Submission #1199454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199454		GoBananas69	Examination (JOI19_examination)	C++20	0 / 100	156 ms	10308 KiB

examination

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

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

vector<int> tree;

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];
}

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 {
        return query(x, L, m, l, m) + query(y, m + 1, R, m + 1, r);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<Query> q(n + k);
    for (int i = 0; i<n; ++i) {
        int s, t;
        cin >> s >> t;
        q[i] = {0, s, t, s + t, -1};
    }
    for (int i = n; i<n + k; ++i) {
        int s, t, sum;
        cin >> s >> t >> sum;
        q[i] = {1, s, t, sum, i - n};
    }
    sort(q.begin(), q.end(), [](const Query &a, const Query &b) {
        return a.s < b.s;
    });
    int sz = 0;
    for (Query &i: q) {
        cout << i.type << ' ' << i.s << ' ' << i.t << ' ' << i.sum << '\n';
        sz = max(sz, i.t);
    }
    sz++;
    tree.resize(4 * sz, 0);
    vector<int> res(k);
    for (Query &i: q) {
        if (i.type == 0) {  
            update(0, 0, sz - 1, i.t);
        } else {
            res[i.idx] = query(0, 0, sz - 1, i.t, sz - 1);
        }
    }
    for (int &i: res) {
        cout << i << ' ';
    }
}

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