Submission #1200841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200841		GoBananas69	Examination (JOI19_examination)	C++20	100 / 100	322 ms	26068 KiB

examination

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Query {
    int type, s, t, sum, idx;
};

struct segment_tree {
    vector<int> tree;
    int n;
    void build(int sz) {
        tree.resize(4 * sz, 0);
        n = sz;
    }
    void update(int i, int L, int R, int p) {
        if (L == R) {
            tree[i]++;
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (p <= m) {
            update(x, L, m, p);
        } else {
            update(y, m + 1, R, p);
        }
        tree[i] = tree[x] + tree[y];
    }
    void update(int p) {
        update(0, 0, n - 1, p);
    }
    int query(int i, int L, int R, int l, int r) {
        if (L == l && r == R) {
            return tree[i];
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return query(x, L, m, l, r);
        } else if (l > m) {
            return query(y, m + 1, R, l, r);
        } else {
            int q1 = query(x, L, m, l, m);
            int q2 = query(y, m + 1, R, m + 1, r);
            return q1 + q2;
        }
    }
    int query(int l, int r) {
        if (l > r) return 0;
        return query(0, 0, n - 1, l, r);
    }
} A, B;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<Query> x(n + k), y(n + k);
    
    // Collect all sum values for compression
    vector<int> all_sums;
    
    for (int i = 0; i < n; ++i) {
        int s, t;
        cin >> s >> t;
        int sum = s + t;
        x[i] = {0, s, t, sum, -1};
        y[i] = {0, s, t, sum, -1};
        all_sums.push_back(sum);
    }
    for (int i = n; i < n + k; ++i) {
        int s, t, sum;
        cin >> s >> t >> sum;
        sum = max(sum, s + t);
        x[i] = {1, s, t, sum, i - n};
        y[i] = {1, s, t, sum, i - n};
        all_sums.push_back(sum);
    }
    
    // Coordinate compression
    sort(all_sums.begin(), all_sums.end());
    all_sums.erase(unique(all_sums.begin(), all_sums.end()), all_sums.end());
    map<int, int> compress;
    for (int i = 0; i < all_sums.size(); ++i) {
        compress[all_sums[i]] = i;
    }
    int compressed_size = all_sums.size();
    
    // Update sums in queries to compressed indices
    for (auto &q : x) q.sum = compress[q.sum];
    for (auto &q : y) q.sum = compress[q.sum];
    
    sort(x.begin(), x.end(), [](const Query &a, const Query &b) {
        if (a.s != b.s) return a.s > b.s;
        return a.type < b.type;
    });
    sort(y.begin(), y.end(), [](const Query &a, const Query &b) {
        if (a.t != b.t) return a.t < b.t;
        return a.type > b.type;
    });
    
    A.build(compressed_size);
    B.build(compressed_size);
    vector<int> ac(k), bc(k);
    
    for (Query &q : x) {
        if (q.type == 0) {
            A.update(q.sum);
        } else if (q.type == 1) {
            ac[q.idx] = A.query(q.sum, compressed_size - 1);
        }
    }
    
    for (Query &q : y) {
        if (q.type == 0) {
            B.update(q.sum);
        } else if (q.type == 1) {
            bc[q.idx] = B.query(q.sum, compressed_size - 1);
        }
    }
    
    for (int i = 0; i < k; ++i) {
        cout << ac[i] - bc[i] << '\n';
    }
}

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