Submission #216202

#	Time	Username	Problem	Language	Result	Execution time	Memory
216202		DS007	Examination (JOI19_examination)	C++14	0 / 100	3096 ms	164472 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mid (l + r) / 2
#define child v * 2
#define index_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>

struct query {
    int x, y, z, i, ans;

    query() {
        x = y = z = i = ans = -1;
    }
};

const int N = 1e5 + 5;
int a[N], b[N];
pair<int, int> s[N];
query qry[N];
int n, q;

index_set t[N * 4];
multimap<int, int> m;

void build(int v, int l, int r) {
    if (l == r) {
        t[v].insert({0, l});
        return;
    }

    build(child, l, mid);
    build(child + 1, mid + 1, r);

    for (auto &i : t[child])
        t[v].insert(i);
    for (auto &i : t[child + 1])
        t[v].insert(i);
}

pair<int, int> update(int v, int l, int r, int tl, int val) {
    if (l == r && l == tl) {
        auto temp = *t[v].begin();
        t[v].clear();
        t[v].insert({val, tl});
        return temp;
    }

    pair<int, int> ret = tl <= mid ? update(child, l, mid, tl, val) : update(child + 1, mid + 1, r, tl, val);
    t[v].erase(ret);
    t[v].insert({val, tl});
    return ret;
}

int query(int v, int l, int r, int tl, int tr, int val) {
    if (tl > tr)
        return 0;
    else if (l == tl && r == tr)
        return t[v].size() - t[v].order_of_key({val, -1});
    return query(child, l, mid, tl, min(mid, tr), val) + query(child + 1, mid + 1, r, max(mid + 1, tl), tr, val);
}

void solveTestCase() {
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> s[i].first >> s[i].second, a[i] = s[i].first, b[i] = s[i].second;
    for (int i = 0; i < q; i++)
        cin >> qry[i].x >> qry[i].y >> qry[i].z, qry[i].i = i;

    build(1, 0, n - 1);
    sort(a, a + n, greater<>());
    sort(b, b + n);
    sort(s, s + n, greater<>());

    sort(qry, qry + q, [](auto &q1, auto &q2) {
        return q1.x > q2.x;
    });

    for (int i = 0; i < n; i++)
        m.insert({b[i], i});

    for (int i = 0, p = 0; i < q; i++) {
        while (p != n && s[p].first >= qry[i].x) {
            auto itr = m.find(s[p].second);
            update(1, 0, n - 1, itr->second, s[p].first + s[p].second);
            m.erase(itr);
            p++;
        }

        int tl = lower_bound(b, b + n, qry[i].y) - b;
        qry[i].ans = query(1, 0, n - 1, tl, n - 1, qry[i].z);
    }

    sort(qry, qry + q, [](auto &q1, auto &q2) {
        return q1.i < q2.i;
    });

    for (int i = 0; i < q; i++)
        cout << qry[i].ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

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