Star's Blog

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6

7
int tr[N * 4];
8

9
void pushup(int u) {
10
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
11
}
12

13
void modify(int u, int l, int r, int p, int val) {
14
    if (l == r) tr[u] += val;
15
    else {
16
        int mid = l + r >> 1;
17
        if (p <= mid) modify(u << 1, l, mid, p, val);
18
        else modify(u << 1 | 1, mid + 1, r, p, val);
19
        pushup(u);
20
    }
21
}
22

23
int query(int u, int l, int r, int k) {
24
    if (l == r) return l;
25
    else {
26
        int mid = l + r >> 1;
27
        if (tr[u << 1] >= k) return query(u << 1, l, mid, k);
28
        else return query(u << 1 | 1, mid + 1, r, k - tr[u << 1]);
29
    }
30
}
31

32
void print(int u, int l, int r) {
33
    if (l == r) printf("%d ", tr[u]);
34
    else {
35
        int mid = l + r >> 1;
36
        print(u << 1, l, mid), print(u << 1 | 1, mid + 1, r);
37
    }
38
}
39

40
int main() {
41
    int n, q;
42
    scanf("%d%d", &n, &q);
43
    for (int i = 1; i <= n; ++i) {
44
        int val;
45
        scanf("%d", &val);
46
        modify(1, 1, n, val, 1);
47
    }
48
    for (int i = 1; i <= q; ++i) {
49
        int val;
50
        scanf("%d", &val);
51
        if (val >= 1 && val <= n) modify(1, 1, n, val, 1);
52
        else modify(1, 1, n, query(1, 1, n, -val), -1);
53
    }
54
    if (tr[1]) printf("%d\n", query(1, 1, n, 1));
55
    else printf("0\n");
56
    return 0;
57
}

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 1000010;
7

8
int main() {
9
    int n, res = 0x3f3f3f3f;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        int a, b;
13
        scanf("%d%d", &a, &b);
14
        res = min(res, a + (b - 1) / 2);
15
    }
16
    printf("%d\n", res);
17
    return 0;
18
}

1
#include <iostream>
2

3
using namespace std;
4

5
int gcd(int a, int b) {
6
    return b ? gcd(b, a % b) : a;
7
}
8

9
int main() {
10
    int n, a, b;
11
    scanf("%d%d%d", &n, &a, &b);
12
    long long t = (long long)a * b / gcd(a, b);
13
    int add = n / a - n / t, dec = n / b - n / t;
14
    printf("%lld\n", (long long)(n + n - add + 1) * add / 2 - (long long)(1 + dec) * dec / 2);
15
    return 0;
16
}

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int MOD = 1000000007; // 从第十场过来的记得改模数qwq
8
const int N = 3010, M = 2000010;
9

10
int power(int n, int p) {
11
    long long res = 1, base = n;
12
    while (p) {
13
        if (p & 1) res = res * base % MOD;
14
        base = base * base % MOD;
15
        p >>= 1;
16
    }
17
    return res;
18
}
19

20
int jc[M], inv[M];
21
int f[N];
22
pair<int, int> p[N];
23

24
int c(int n, int m) {
25
    return 1LL * jc[n] * inv[m] % MOD * inv[n - m] % MOD;
26
}
27

28
int way(pair<int, int> a, pair<int, int> b) {
29
    return c(b.second + b.first - a.second - a.first, b.second - a.second);
30
}
31

32
bool le(pair<int, int> a, pair<int, int> b) {
33
    return a.first <= b.first && a.second <= b.second;
34
}
35

36
int main() {
37
    jc[0] = inv[0] = 1;
38
    for (int i = 1; i <= 2000000; ++i) {
39
        jc[i] = 1LL * jc[i - 1] * i % MOD;
40
        inv[i] = power(jc[i], MOD - 2);
41
    }
42
    int n, m, k;
43
    scanf("%d%d%d", &n, &m, &k);
44
    for (int i = 1; i <= k; ++i) {
45
        scanf("%d%d", &p[i].first, &p[i].second);
46
    }
47
    sort(p + 1, p + k + 1);
48
    p[k + 1] = {m, n};
49
    p[0] = {1, 1};
50
    f[0] = 1;
51
    for (int i = 1; i <= k + 1; ++i) {
52
        f[i] = way(p[0], p[i]);
53
        for (int j = 1; j < i; ++j) {
54
            if (le(p[j], p[i])) {
55
                f[i] = (f[i] - (1LL * f[j] * way(p[j], p[i]) % MOD) + MOD) % MOD;
56
            }
57
        }
58
    }
59
    printf("%d\n", f[k + 1]);
60
    return 0;
61
}