Submission #1271738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271738		ducanh0811	Examination (JOI19_examination)	C++20	100 / 100	220 ms	11324 KiB

examination

#include <bits/stdc++.h>
#define left OK1207
#define right KO0712
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 100005
int n, q;
int res[MAXN];
struct event {
    int x, y, z, i;
};
vector<event> query;
vector<int> compZ;

struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n = 0){
        n = _n;
        bit.assign(n + 5, 0);
    }

    void upd(int p, int val){
        for (; p <= n; p += p & -p) bit[p] += val;
    }

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

    int get(int u, int v){
        return get(v) - get(u - 1);
    }
} bit;

void compression(){
    for (event &x : query){
        compZ.push_back(x.z);
    }
    sort(compZ.begin(), compZ.end());
    compZ.erase(unique(compZ.begin(), compZ.end()), compZ.end());
    bit = BIT(compZ.size());
    for (event &x : query){
        x.z = lower_bound(compZ.begin(), compZ.end(), x.z) - compZ.begin() + 1;
    }
}

void CDQ(int l, int r){
    if (l == r) return;
    int mid = (l + r) >> 1;
    vector<event> left, right;
    FOR(i, l, mid){
        if (query[i - 1].i == 0) left.push_back(query[i - 1]);
    }
    FOR(i, mid + 1, r){
        if (query[i - 1].i != 0) right.push_back(query[i - 1]);
    }
    sort(left.begin(), left.end(), [](const event &a, const event &b){
        return a.y > b.y;
    });
    sort(right.begin(), right.end(), [](const event &a, const event &b){
        return a.y > b.y;
    });
    int ptr = 0;
    for (event &x : right){
        while (ptr < (int)left.size() && left[ptr].y >= x.y){
            bit.upd(left[ptr].z, 1);
            ptr++;
        }
        res[x.i] += bit.get(x.z, compZ.size());
    }
    FOR(i, 0, ptr - 1) {
        bit.upd(left[i].z, -1);
    }
    CDQ(l, mid);
    CDQ(mid + 1, r);
}

void solve(){
    cin >> n >> q;
    FOR(i, 1, n){
        int x, y; cin >> x >> y;
        query.push_back({x, y, x + y, 0});
    }
    FOR(i, 1, q){
        int x, y, z; cin >> x >> y >> z;
        query.push_back({x, y, z, i});
    }
    sort(query.begin(), query.end(), [](const event &a, const event &b){
        if (a.x != b.x) return a.x > b.x;
        if (a.y != b.y) return a.y > b.y;
        if (a.z != b.z) return a.z > b.z;
        return a.i < b.i;
    });
    compression();
    CDQ(1, query.size());
    FOR(i, 1, q){
        cout << res[i] << '\n';
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57