Submission #1271742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271742		orzorzorz	Examination (JOI19_examination)	C++20	100 / 100	475 ms	29668 KiB

examination

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int type; // 0 = student, 1 = query
    long long x, y, z; 
    int id;   // query id
};

struct BIT {
    vector<int> bit;
    int n;
    BIT(int n) : n(n), bit(n+1, 0) {}
    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    int rangeSum(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l-1);
    }
};

vector<Node> nodes;
vector<int> ans;
BIT *bit;
vector<long long> allZ; // for compression

void cdq(int l, int r) {
    if (r - l <= 1) return;
    int m = (l + r) >> 1;
    cdq(l, m);
    cdq(m, r);

    vector<Node> left, right;
    for (int i = l; i < m; i++) left.push_back(nodes[i]);
    for (int i = m; i < r; i++) right.push_back(nodes[i]);

    sort(left.begin(), left.end(), [](auto &a, auto &b){ return a.y < b.y; });
    sort(right.begin(), right.end(), [](auto &a, auto &b){ return a.y < b.y; });

    int i = 0;
    for (auto &q : right) {
        while (i < (int)left.size() && left[i].y <= q.y) {
            if (left[i].type == 0) {
                int pos = lower_bound(allZ.begin(), allZ.end(), left[i].z) - allZ.begin() + 1;
                bit->add(pos, 1);
            }
            i++;
        }
        if (q.type == 1) {
            int pos = lower_bound(allZ.begin(), allZ.end(), q.z) - allZ.begin() + 1;
            ans[q.id] += bit->sum(pos);
        }
    }

    // rollback BIT
    for (int j = 0; j < i; j++) {
        if (left[j].type == 0) {
            int pos = lower_bound(allZ.begin(), allZ.end(), left[j].z) - allZ.begin() + 1;
            bit->add(pos, -1);
        }
    }

    inplace_merge(nodes.begin() + l, nodes.begin() + m, nodes.begin() + r, 
                  [](auto &a, auto &b){ return a.y < b.y; });
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<long long> S(N), T(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> T[i];
        long long U = S[i] + T[i];
        nodes.push_back({0, -S[i], -T[i], -U, -1});
        allZ.push_back(-U);
    }
    ans.assign(Q, 0);
    for (int j = 0; j < Q; j++) {
        long long X, Y, Z;
        cin >> X >> Y >> Z;
        nodes.push_back({1, -X, -Y, -Z, j});
        allZ.push_back(-Z);
    }
    sort(allZ.begin(), allZ.end());
    allZ.erase(unique(allZ.begin(), allZ.end()), allZ.end());

    sort(nodes.begin(), nodes.end(), [](auto &a, auto &b){
        if (a.x != b.x) return a.x < b.x;
        return a.type < b.type;
    });

    bit = new BIT(allZ.size() + 5);
    cdq(0, nodes.size());

    for (int j = 0; j < Q; j++) cout << ans[j] << "\n";
}

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