oj.uz

Submission #613658

# Submission time Handle Problem Language Result Execution time Memory
613658 2022-07-30T08:58:05 Z tengiz05 Examination (JOI19_examination) C++17
100 / 100
 1006 ms 276108 KB 
#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

constexpr int N = 100000;

struct Node {
    int s;
    Node *l, *r;
    Node() : s(0), l(nullptr), r(nullptr) {}
};
Node *r[N + 1];
void add(Node *&p, int l, int r, int x) {
    if (p == nullptr) {
        p = new Node();
    }
    p->s++;
    if (l == r - 1) {
        return;
    }
    int m = (l + r) / 2;
    if (x < m) {
        add(p->l, l, m, x);
    } else {
        add(p->r, m, r, x);
    }
}
int query(Node *p, int l, int r, int x) {
    if (p == nullptr || r <= x)
        return 0;
    if (x <= l) {
        return p->s;
    }
    int m = (l + r) / 2;
    return query(p->l, l, m, x) + query(p->r, m, r, x);
}
void addPoint(int x, int y) {
    x = N - x - 1;
    for (int i = x + 1; i <= N; i += i & -i) {
        add(r[i], 0, N, y);
    }
}
int ask(int x, int y) {
    x = N - x - 1;
    int ans = 0;
    for (int i = x + 1; i > 0; i -= i & -i) {
        ans += query(r[i], 0, N, y);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n), b(n), c(n);
    
    vector<int> A, B, C;
    
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        c[i] = a[i] + b[i];
        A.push_back(a[i]);
        B.push_back(b[i]);
        C.push_back(c[i]);
    }
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(A.begin(), A.end(), a[i]) - A.begin();
        b[i] = lower_bound(B.begin(), B.end(), b[i]) - B.begin();
        c[i] = lower_bound(C.begin(), C.end(), c[i]) - C.begin();
    }
    
    vector<int> x(q), y(q), z(q);
    
    for (int i = 0; i < q; i++) {
        cin >> x[i] >> y[i] >> z[i];
        x[i] = lower_bound(A.begin(), A.end(), x[i]) - A.begin();
        y[i] = lower_bound(B.begin(), B.end(), y[i]) - B.begin();
        z[i] = lower_bound(C.begin(), C.end(), z[i]) - C.begin();
        
    }
    
    vector<array<int, 3>> p;
    for (int i = 0; i < n; i++) {
        p.push_back({c[i], i, 0});
    }
    for (int i = 0; i < q; i++) {
        p.push_back({z[i], i, 1});
    }
    
    sort(p.begin(), p.end(), [&](const auto &a, const auto &b) {
        if (a[0] == b[0]) {
            return a[2] < b[2];
        } else {
            return a[0] > b[0];
        }
    });
    
    vector<int> ans(q);
    
    for (auto [_, i, gg] : p) {
        if (gg == 0) {
            addPoint(a[i], b[i]);
        } else {
            ans[i] = ask(x[i], y[i]);
        }
    }
    
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 12 ms 5260 KB Output is correct
8 Correct 13 ms 5332 KB Output is correct
9 Correct 14 ms 5324 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 15 ms 5204 KB Output is correct
14 Correct 13 ms 5228 KB Output is correct
15 Correct 13 ms 5280 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 6 ms 2260 KB Output is correct
18 Correct 2 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 239204 KB Output is correct
2 Correct 935 ms 238920 KB Output is correct
3 Correct 874 ms 239172 KB Output is correct
4 Correct 304 ms 53640 KB Output is correct
5 Correct 199 ms 28088 KB Output is correct
6 Correct 101 ms 8332 KB Output is correct
7 Correct 869 ms 238768 KB Output is correct
8 Correct 862 ms 238848 KB Output is correct
9 Correct 705 ms 238720 KB Output is correct
10 Correct 137 ms 12400 KB Output is correct
11 Correct 213 ms 42608 KB Output is correct
12 Correct 61 ms 8312 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 239204 KB Output is correct
2 Correct 935 ms 238920 KB Output is correct
3 Correct 874 ms 239172 KB Output is correct
4 Correct 304 ms 53640 KB Output is correct
5 Correct 199 ms 28088 KB Output is correct
6 Correct 101 ms 8332 KB Output is correct
7 Correct 869 ms 238768 KB Output is correct
8 Correct 862 ms 238848 KB Output is correct
9 Correct 705 ms 238720 KB Output is correct
10 Correct 137 ms 12400 KB Output is correct
11 Correct 213 ms 42608 KB Output is correct
12 Correct 61 ms 8312 KB Output is correct
13 Correct 835 ms 239388 KB Output is correct
14 Correct 956 ms 239496 KB Output is correct
15 Correct 872 ms 239164 KB Output is correct
16 Correct 305 ms 53820 KB Output is correct
17 Correct 195 ms 28132 KB Output is correct
18 Correct 89 ms 8308 KB Output is correct
19 Correct 806 ms 239304 KB Output is correct
20 Correct 841 ms 239456 KB Output is correct
21 Correct 751 ms 239292 KB Output is correct
22 Correct 128 ms 12412 KB Output is correct
23 Correct 208 ms 42440 KB Output is correct
24 Correct 54 ms 8292 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 12 ms 5260 KB Output is correct
8 Correct 13 ms 5332 KB Output is correct
9 Correct 14 ms 5324 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 15 ms 5204 KB Output is correct
14 Correct 13 ms 5228 KB Output is correct
15 Correct 13 ms 5280 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 6 ms 2260 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1006 ms 239204 KB Output is correct
20 Correct 935 ms 238920 KB Output is correct
21 Correct 874 ms 239172 KB Output is correct
22 Correct 304 ms 53640 KB Output is correct
23 Correct 199 ms 28088 KB Output is correct
24 Correct 101 ms 8332 KB Output is correct
25 Correct 869 ms 238768 KB Output is correct
26 Correct 862 ms 238848 KB Output is correct
27 Correct 705 ms 238720 KB Output is correct
28 Correct 137 ms 12400 KB Output is correct
29 Correct 213 ms 42608 KB Output is correct
30 Correct 61 ms 8312 KB Output is correct
31 Correct 835 ms 239388 KB Output is correct
32 Correct 956 ms 239496 KB Output is correct
33 Correct 872 ms 239164 KB Output is correct
34 Correct 305 ms 53820 KB Output is correct
35 Correct 195 ms 28132 KB Output is correct
36 Correct 89 ms 8308 KB Output is correct
37 Correct 806 ms 239304 KB Output is correct
38 Correct 841 ms 239456 KB Output is correct
39 Correct 751 ms 239292 KB Output is correct
40 Correct 128 ms 12412 KB Output is correct
41 Correct 208 ms 42440 KB Output is correct
42 Correct 54 ms 8292 KB Output is correct
43 Correct 879 ms 275932 KB Output is correct
44 Correct 862 ms 276008 KB Output is correct
45 Correct 949 ms 276108 KB Output is correct
46 Correct 330 ms 75336 KB Output is correct
47 Correct 232 ms 34948 KB Output is correct
48 Correct 85 ms 8428 KB Output is correct
49 Correct 814 ms 275976 KB Output is correct
50 Correct 785 ms 276028 KB Output is correct
51 Correct 746 ms 275996 KB Output is correct
52 Correct 163 ms 15656 KB Output is correct
53 Correct 244 ms 62556 KB Output is correct