Submission #1193198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193198		GoBananas69	Examination (JOI19_examination)	C++20	0 / 100	3093 ms	22172 KiB

examination

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;

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

vector<Query> queries;
vector<vector<ll>> st;

void update(int i, int L, int R, int p, int v) {
    if (L == R) {
        st[i].push_back(v);
        return;
    }
    int m = (L + R) / 2;
    int x = 2 * i + 1, y = x + 1;
    if (p <= m) {
        update(x, L, m, p, v);
    } else {
        update(y, m + 1, R, p, v);
    }
    st[i].clear();
    merge(st[x].begin(), st[x].end(), st[y].begin(), st[y].end(), back_inserter(st[i]));
}

int query(int i, int L, int R, int l, int r, int v) {
    if (L == l && r == R) {
        auto it = upper_bound(st[i].begin(), st[i].end(), v);
        return int(st[i].end() - it);
    }

    int m = (L + R) / 2;
    int x = 2 * i + 1, y = x + 1;
    if (r <= m) {
        return query(x, L, m, l, r, v);
    } else if (l > m) {
        return query(y, m + 1, R, l, r, v);
    } else {
        int q1 = query(x, L, m, l, m, v);
        int q2 = query(y, m + 1, R, m + 1, r, v);
        return q1 + q2;
    }
}

signed main() {
    int n, k;
    cin >> n >> k;
    queries.resize(n + k);
    for (int i = 0; i < n; ++i) {
        cin >> queries[i].s >> queries[i].t;
        queries[i].type = 0;
        queries[i].sum = queries[i].s + queries[i].t;
    }
    for (int i = n; i < n + k; ++i) {
        cin >> queries[i].s >> queries[i].t >> queries[i].sum;
        queries[i].idx = i - n;
        queries[i].type = 1;
    }
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
        if (a.s != b.s) return a.s > b.s;
        if (a.t != b.t) return a.t > b.t;
        return a.sum > b.sum;
    });

    int sz = 0;

    for (Query &q : queries) {
        // cout << q.type << ' ' << q.s << ' ' << q.t << ' ' << q.sum << '\n';
        sz = max(sz, q.t);
    }

    st.resize(4 * sz + 5);

    vector<int> res(k);

    for (Query &q : queries) {
        int type = q.type;
        if (type == 0) {
            update(0, 0, sz, q.t, q.sum);
        } else {
            int cnt = query(0, 0, sz, q.t, sz, q.sum);
            res[q.idx] = cnt;
        }
    }
    for (int &i : res) {
        cout << i << '\n';
    }
}

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