oj.uz

Submission #997994

# Submission time Handle Problem Language Result Execution time Memory
997994 2024-06-13T07:36:12 Z toan2602 Examination (JOI19_examination) C++14
43 / 100
 1089 ms 94840 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
int n, d = 0, q, x[100005], y[100005], z[100005], cnt[200005];
bool mark[500005], Q[500005];
set<int> s;

struct NODE {
    int x, y, z, idx;
    bool operator < (NODE b) {
        if(x != b.x) return x < b.x;
        else if(y != b.y) return y < b.y;
        else if(z != b.z) return z < b.z;
        else return idx > b.idx;
    }
} node[500005];

int bit[500005];

void update(int pos, int val) {
    while(pos <= d) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int res = 0;
    while(pos > 0) {
        res += bit[pos];
        pos -= pos & -pos;
    }
    return res;
}

int range(int l, int r) {
    return get(r) - get(l-1);
}

void cdq(int l, int r) {
    int mid = (l + r) / 2;
    if(l == r) return;
    cdq(l, mid);
    cdq(mid + 1, r);
    for (int i = mid + 1; i <= r; i++) {
        if(!Q[node[i].idx]) update(node[i].z, 1);
    }
    vector<NODE> v;
    int p1;
    p1 = mid+1;
    for (int i = l; i <= mid; i++) {
        while(p1 <= r && node[p1].y <= node[i].y) {
            v.push_back(node[p1]);
            if(!Q[node[p1].idx]) update(node[p1].z, -1);
            p1++;
        }
        v.push_back(node[i]);
        cnt[node[i].idx] += range(node[i].z+1, d);
    }
    while(p1 <= r) {
        v.push_back(node[p1]);
        if(!Q[node[p1].idx]) update(node[p1].z, -1);
        p1++;
    }
    for (int i = l; i <= r; i++) {
        node[i] = v[i-l];
    }
    return;
}
map<int, int> mp;

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> node[i].x >> node[i].y;
        node[i].z = node[i].x + node[i].y;
        s.insert(node[i].x);
        s.insert(node[i].y);
        s.insert(node[i].z);
        node[i].idx = i;
    }
    for (int i = 1; i <= q; i++) {
        cin >> x[i] >> y[i] >> z[i];
        y[i]--, z[i]--;
        s.insert(x[i]);
        s.insert(y[i]);
        s.insert(z[i]);
    }
    for (int i: s) mp[i] = ++d;
    for (int i = 1; i <= n; i++) {
        node[i].x = mp[node[i].x];
        node[i].y = mp[node[i].y];
        node[i].z = mp[node[i].z];
        //cout << node[i].x << ' ' << node[i].y << ' ' << node[i].z << '\n';
    }
    for (int i = 1; i <= q; i++) {
        x[i] = mp[x[i]];
        y[i] = mp[y[i]];
        z[i] = mp[z[i]];
        node[i+n] = {x[i], y[i], z[i], i + n};
        Q[i+n] = true;
    }
    sort(node + 1, node + 1 + q + n);
    cdq(1, n+q);
    for (int i = 1; i <= q; i++) {
        cout << cnt[i+n] << '\n';
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 17 ms 9172 KB Output is correct
8 Correct 16 ms 9116 KB Output is correct
9 Correct 17 ms 9084 KB Output is correct
10 Correct 12 ms 8264 KB Output is correct
11 Correct 12 ms 8348 KB Output is correct
12 Correct 8 ms 7068 KB Output is correct
13 Correct 14 ms 8756 KB Output is correct
14 Correct 13 ms 8736 KB Output is correct
15 Correct 14 ms 8736 KB Output is correct
16 Correct 8 ms 7652 KB Output is correct
17 Correct 14 ms 7972 KB Output is correct
18 Correct 6 ms 7068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 43608 KB Output is correct
2 Correct 514 ms 43908 KB Output is correct
3 Correct 465 ms 45748 KB Output is correct
4 Correct 354 ms 40108 KB Output is correct
5 Correct 358 ms 40028 KB Output is correct
6 Correct 157 ms 28744 KB Output is correct
7 Correct 454 ms 44196 KB Output is correct
8 Correct 479 ms 45388 KB Output is correct
9 Correct 461 ms 43096 KB Output is correct
10 Correct 353 ms 39108 KB Output is correct
11 Correct 316 ms 39856 KB Output is correct
12 Correct 132 ms 28720 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 43608 KB Output is correct
2 Correct 514 ms 43908 KB Output is correct
3 Correct 465 ms 45748 KB Output is correct
4 Correct 354 ms 40108 KB Output is correct
5 Correct 358 ms 40028 KB Output is correct
6 Correct 157 ms 28744 KB Output is correct
7 Correct 454 ms 44196 KB Output is correct
8 Correct 479 ms 45388 KB Output is correct
9 Correct 461 ms 43096 KB Output is correct
10 Correct 353 ms 39108 KB Output is correct
11 Correct 316 ms 39856 KB Output is correct
12 Correct 132 ms 28720 KB Output is correct
13 Correct 642 ms 47336 KB Output is correct
14 Correct 556 ms 44800 KB Output is correct
15 Correct 505 ms 43912 KB Output is correct
16 Correct 478 ms 39124 KB Output is correct
17 Correct 419 ms 40400 KB Output is correct
18 Correct 188 ms 28144 KB Output is correct
19 Correct 585 ms 46660 KB Output is correct
20 Correct 560 ms 46648 KB Output is correct
21 Correct 561 ms 47652 KB Output is correct
22 Correct 299 ms 39200 KB Output is correct
23 Correct 309 ms 37572 KB Output is correct
24 Correct 136 ms 28404 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 17 ms 9172 KB Output is correct
8 Correct 16 ms 9116 KB Output is correct
9 Correct 17 ms 9084 KB Output is correct
10 Correct 12 ms 8264 KB Output is correct
11 Correct 12 ms 8348 KB Output is correct
12 Correct 8 ms 7068 KB Output is correct
13 Correct 14 ms 8756 KB Output is correct
14 Correct 13 ms 8736 KB Output is correct
15 Correct 14 ms 8736 KB Output is correct
16 Correct 8 ms 7652 KB Output is correct
17 Correct 14 ms 7972 KB Output is correct
18 Correct 6 ms 7068 KB Output is correct
19 Correct 478 ms 43608 KB Output is correct
20 Correct 514 ms 43908 KB Output is correct
21 Correct 465 ms 45748 KB Output is correct
22 Correct 354 ms 40108 KB Output is correct
23 Correct 358 ms 40028 KB Output is correct
24 Correct 157 ms 28744 KB Output is correct
25 Correct 454 ms 44196 KB Output is correct
26 Correct 479 ms 45388 KB Output is correct
27 Correct 461 ms 43096 KB Output is correct
28 Correct 353 ms 39108 KB Output is correct
29 Correct 316 ms 39856 KB Output is correct
30 Correct 132 ms 28720 KB Output is correct
31 Correct 642 ms 47336 KB Output is correct
32 Correct 556 ms 44800 KB Output is correct
33 Correct 505 ms 43912 KB Output is correct
34 Correct 478 ms 39124 KB Output is correct
35 Correct 419 ms 40400 KB Output is correct
36 Correct 188 ms 28144 KB Output is correct
37 Correct 585 ms 46660 KB Output is correct
38 Correct 560 ms 46648 KB Output is correct
39 Correct 561 ms 47652 KB Output is correct
40 Correct 299 ms 39200 KB Output is correct
41 Correct 309 ms 37572 KB Output is correct
42 Correct 136 ms 28404 KB Output is correct
43 Incorrect 1089 ms 94840 KB Output isn't correct
44 Halted 0 ms 0 KB -