Submission #997994

#	Time	Username	Problem	Language	Result	Execution time	Memory
997994		toan2602	Examination (JOI19_examination)	C++14	43 / 100	1089 ms	94840 KiB

examination

#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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 0 / 57