oj.uz

Submission #997989

# Submission time Handle Problem Language Result Execution time Memory
997989 2024-06-13T07:33:27 Z toan2602 Examination (JOI19_examination) C++14
0 / 100
 477 ms 44216 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];
        x[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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 44216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 44216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -