oj.uz

Submission #1110753

# Submission time Handle Problem Language Result Execution time Memory
1110753 2024-11-10T10:50:07 Z anmattroi Examination (JOI19_examination) C++14
100 / 100
 417 ms 57180 KB 
#include <bits/stdc++.h>

#define maxn 100005
#define fi first
#define se second

using namespace std;
using ii = pair<int, int>;

int n, q;

int itone[22*maxn], ittwo[22*maxn], Lone[22*maxn], Ltwo[22*maxn], Rone[22*maxn], Rtwo[22*maxn];
int rootone[maxn], roottwo[maxn], ntone = 0, nttwo = 0;

int buildone(int lo = 1, int hi = n) {
    if (lo == hi) return ++ntone;
    int cur = ++ntone, mid = (lo + hi) >> 1;
    Lone[cur] = buildone(lo, mid);
    Rone[cur] = buildone(mid+1, hi);
    return cur;
}

int buildtwo(int lo = 1, int hi = n) {
    if (lo == hi) return ++nttwo;
    int cur = ++nttwo, mid = (lo + hi) >> 1;
    Ltwo[cur] = buildtwo(lo, mid);
    Rtwo[cur] = buildtwo(mid+1, hi);
    return cur;
}

int updone(int u, int oldver, int lo = 1, int hi = n) {
    if (lo == hi) {
        itone[++ntone] = itone[oldver] + 1;
        return ntone;
    }
    int cur = ++ntone, mid = (lo + hi) >> 1;
    if (u <= mid) {
        Lone[cur] = updone(u, Lone[oldver], lo, mid);
        Rone[cur] = Rone[oldver];
    } else {
        Lone[cur] = Lone[oldver];
        Rone[cur] = updone(u, Rone[oldver], mid+1, hi);
    }
    itone[cur] = itone[Lone[cur]] + itone[Rone[cur]];
    return cur;
}

int updtwo(int u, int oldver, int lo = 1, int hi = n) {
    if (lo == hi) {
        ittwo[++nttwo] = ittwo[oldver] + 1;
        return nttwo;
    }
    int cur = ++nttwo, mid = (lo + hi) >> 1;
    if (u <= mid) {
        Ltwo[cur] = updtwo(u, Ltwo[oldver], lo, mid);
        Rtwo[cur] = Rtwo[oldver];
    } else {
        Ltwo[cur] = Ltwo[oldver];
        Rtwo[cur] = updtwo(u, Rtwo[oldver], mid+1, hi);
    }
    ittwo[cur] = ittwo[Ltwo[cur]] + ittwo[Rtwo[cur]];
    return cur;
}

int getone(int u, int v, int r, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return itone[r];
    int mid = (lo + hi) >> 1;
    return getone(u, v, Lone[r], lo, mid) + getone(u, v, Rone[r], mid+1, hi);
}

int gettwo(int u, int v, int r, int lo = 1, int hi = n) {
    if (u > hi || v < lo) return 0;
    if (u <= lo && hi <= v) return ittwo[r];
    int mid = (lo + hi) >> 1;
    return gettwo(u, v, Ltwo[r], lo, mid) + gettwo(u, v, Rtwo[r], mid+1, hi);
}

ii a[maxn];

int b[maxn], c[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
        b[i] = a[i].se;
        c[i] = a[i].fi + a[i].se;
    }
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);

    sort(a + 1, a + n + 1);

    rootone[0] = buildone();
    roottwo[0] = buildtwo();

    for (int i = 1; i <= n; i++) {
        int p1 = lower_bound(b + 1, b + n + 1, a[i].se) - b,
            p2 = lower_bound(c + 1, c + n + 1, a[i].fi+a[i].se) - c;
        rootone[i] = updone(p1, rootone[i-1]);
        roottwo[i] = updtwo(p2, roottwo[i-1]);
    }

    auto solve = [&]() -> void {
        int x, y, z;
        cin >> x >> y >> z;
        int L1 = lower_bound(a + 1, a + n + 1, ii{x, 0}) - a;

        if (L1 > n) {
            cout << "0\n";
            return;
        }

        int lo = L1-1, hi = n+1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (a[mid].fi + y >= z) hi = mid;
            else lo = mid;
        }
        int p1 = lower_bound(b + 1, b + n + 1, y) - b, p2 = lower_bound(c + 1, c + n + 1, z) - c;

        int ans = 0;
        if (p2 <= n) ans += gettwo(p2, n, roottwo[lo]) - gettwo(p2, n, roottwo[L1-1]);
        if (p1 <= n) ans += getone(p1, n, rootone[n]) - getone(p1, n, rootone[lo]);

        cout << ans << "\n";
    };

    while (q--) solve();
}
/*
5 4
20 95
35 100
45 15
70 70
80 40
20 50 120
10 10 100
60 60 80
0 100 100
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct
2 Correct 2 ms 10576 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 10 ms 11088 KB Output is correct
8 Correct 7 ms 11088 KB Output is correct
9 Correct 7 ms 11212 KB Output is correct
10 Correct 6 ms 11088 KB Output is correct
11 Correct 6 ms 11088 KB Output is correct
12 Correct 4 ms 11260 KB Output is correct
13 Correct 9 ms 11088 KB Output is correct
14 Correct 5 ms 11088 KB Output is correct
15 Correct 6 ms 11088 KB Output is correct
16 Correct 4 ms 11036 KB Output is correct
17 Correct 6 ms 11260 KB Output is correct
18 Correct 3 ms 11088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 54856 KB Output is correct
2 Correct 242 ms 54764 KB Output is correct
3 Correct 263 ms 54872 KB Output is correct
4 Correct 156 ms 54088 KB Output is correct
5 Correct 170 ms 54088 KB Output is correct
6 Correct 86 ms 53320 KB Output is correct
7 Correct 228 ms 54856 KB Output is correct
8 Correct 228 ms 54344 KB Output is correct
9 Correct 209 ms 54600 KB Output is correct
10 Correct 115 ms 53832 KB Output is correct
11 Correct 115 ms 54132 KB Output is correct
12 Correct 54 ms 53064 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 54856 KB Output is correct
2 Correct 242 ms 54764 KB Output is correct
3 Correct 263 ms 54872 KB Output is correct
4 Correct 156 ms 54088 KB Output is correct
5 Correct 170 ms 54088 KB Output is correct
6 Correct 86 ms 53320 KB Output is correct
7 Correct 228 ms 54856 KB Output is correct
8 Correct 228 ms 54344 KB Output is correct
9 Correct 209 ms 54600 KB Output is correct
10 Correct 115 ms 53832 KB Output is correct
11 Correct 115 ms 54132 KB Output is correct
12 Correct 54 ms 53064 KB Output is correct
13 Correct 381 ms 55276 KB Output is correct
14 Correct 385 ms 55112 KB Output is correct
15 Correct 233 ms 54760 KB Output is correct
16 Correct 210 ms 54600 KB Output is correct
17 Correct 245 ms 54356 KB Output is correct
18 Correct 105 ms 53320 KB Output is correct
19 Correct 331 ms 55232 KB Output is correct
20 Correct 377 ms 55276 KB Output is correct
21 Correct 370 ms 55368 KB Output is correct
22 Correct 113 ms 53832 KB Output is correct
23 Correct 109 ms 54084 KB Output is correct
24 Correct 55 ms 53084 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct
2 Correct 2 ms 10576 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 10 ms 11088 KB Output is correct
8 Correct 7 ms 11088 KB Output is correct
9 Correct 7 ms 11212 KB Output is correct
10 Correct 6 ms 11088 KB Output is correct
11 Correct 6 ms 11088 KB Output is correct
12 Correct 4 ms 11260 KB Output is correct
13 Correct 9 ms 11088 KB Output is correct
14 Correct 5 ms 11088 KB Output is correct
15 Correct 6 ms 11088 KB Output is correct
16 Correct 4 ms 11036 KB Output is correct
17 Correct 6 ms 11260 KB Output is correct
18 Correct 3 ms 11088 KB Output is correct
19 Correct 243 ms 54856 KB Output is correct
20 Correct 242 ms 54764 KB Output is correct
21 Correct 263 ms 54872 KB Output is correct
22 Correct 156 ms 54088 KB Output is correct
23 Correct 170 ms 54088 KB Output is correct
24 Correct 86 ms 53320 KB Output is correct
25 Correct 228 ms 54856 KB Output is correct
26 Correct 228 ms 54344 KB Output is correct
27 Correct 209 ms 54600 KB Output is correct
28 Correct 115 ms 53832 KB Output is correct
29 Correct 115 ms 54132 KB Output is correct
30 Correct 54 ms 53064 KB Output is correct
31 Correct 381 ms 55276 KB Output is correct
32 Correct 385 ms 55112 KB Output is correct
33 Correct 233 ms 54760 KB Output is correct
34 Correct 210 ms 54600 KB Output is correct
35 Correct 245 ms 54356 KB Output is correct
36 Correct 105 ms 53320 KB Output is correct
37 Correct 331 ms 55232 KB Output is correct
38 Correct 377 ms 55276 KB Output is correct
39 Correct 370 ms 55368 KB Output is correct
40 Correct 113 ms 53832 KB Output is correct
41 Correct 109 ms 54084 KB Output is correct
42 Correct 55 ms 53084 KB Output is correct
43 Correct 398 ms 57180 KB Output is correct
44 Correct 375 ms 57160 KB Output is correct
45 Correct 417 ms 56648 KB Output is correct
46 Correct 262 ms 55632 KB Output is correct
47 Correct 316 ms 55624 KB Output is correct
48 Correct 93 ms 53320 KB Output is correct
49 Correct 313 ms 57160 KB Output is correct
50 Correct 342 ms 57160 KB Output is correct
51 Correct 327 ms 57064 KB Output is correct
52 Correct 160 ms 55532 KB Output is correct
53 Correct 119 ms 54856 KB Output is correct