Submission #1073351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073351		Szil	Examination (JOI19_examination)	C++17	100 / 100	1372 ms	123916 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using ll = long long;
using namespace std;
using namespace __gnu_pbds;
using indexed_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;

const int MAXN = 100'001;

indexed_set t[4*MAXN];
int val[MAXN], ans[MAXN], n, q;

void sequpd(int u, int k) {
    u += n;
    for (;u >= 1; u /= 2) {
        t[u].insert(k);
    }
}

int segqry(int l, int r, int k) {
    int res = 0;
    l += n; r += n;
    while (l <= r) {
        if (l % 2 == 1) {
            res += t[l].size() - t[l].order_of_key(k);
            l++;
        }
        if (r % 2 == 0) {
            res += t[r].size() - t[r].order_of_key(k);
            r--;
        }
        l /= 2; r /= 2;
    }
    return res;
}

void solve() {
    cin >> n >> q;
    vector<array<int, 3>> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
        v[i][2] = -1;
    }
    sort(v.begin(), v.end(), [](auto a, auto b){
        return a[1] < b[1];
    });
    for (int i = 0; i < n; i++) {
        v[i][2] = i+1;
        val[i+1] = v[i][1];
    }
    sort(v.begin(), v.end(), [](auto a, auto b){
        return a[0] > b[0];
    });
    vector<array<int, 4>> qrys(q);
    for (int i = 0; i < q; i++) {
        cin >> qrys[i][0] >> qrys[i][1] >> qrys[i][2];
        qrys[i][3] = i;
    }
    sort(qrys.begin(), qrys.end(), [](auto a, auto b){
        return a[0] > b[0];
    });
    int idx = 0;
    for (auto [x, y, z, i] : qrys) {
        while (idx < n && v[idx][0] >= x) {
            sequpd(v[idx][2], v[idx][0] + v[idx][1]);
            idx++;
        }
        int pos = lower_bound(val+1, val+n+1, y) - val;
        ans[i] = segqry(pos, n, z);
    }

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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