Submission #1135260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135260		antonn	Examination (JOI19_examination)	C++20	100 / 100	1592 ms	206104 KiB

examination

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using oset = tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 7;

int n, q;
oset t[8*N];

void update(int v, int tl, int tr, int p, pi val) {
    t[v].insert(val);
    if (tl < tr) {
        int tm = (tl + tr) / 2;
        if (p <= tm) update(2 * v, tl, tm, p, val);
        if (p > tm) update(2 * v + 1, tm + 1, tr, p, val);
    }
}

int get(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return t[v].size() - t[v].order_of_key({x, -1});
    int tm = (tl + tr) / 2;
    return get(2 * v, tl, tm, l, r, x) + get(2 * v + 1, tm + 1, tr, l, r, x);
}

void update(int p, int x, int ind) {
    update(1, 1, n+q, p, {x, ind});
}

int get(int p, int x) {
    return get(1, 1, n+q, p, n+q, x);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> q;
    vector<pi> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].F >> a[i].S;
    sort(a.begin(), a.end());
    
    vector<array<int, 4>> qs;
    for (int i = 0; i < q; ++i) {
        int a, b, c; 
        cin >> a >> b >> c;
        qs.push_back({a, b, c, i});
    }
    sort(qs.begin(), qs.end());
    
    map<int, int> id;
    vector<int> vals;
    for (int i = 0; i < n; ++i) vals.push_back(a[i].S);
    for (int i = 0; i < q; ++i) vals.push_back(qs[i][1]);
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    for (int i = 0; i < vals.size(); ++i) id[vals[i]] = i + 1;
    
    vector<int> sol(q);
    int j = n - 1;
    for (int i = q - 1; i >= 0; --i) {
        while (j >= 0 && a[j].F >= qs[i][0]) {
            update(id[a[j].S], a[j].S+a[j].F, j); 
            --j;
        }
        sol[qs[i][3]] = get(id[qs[i][1]], qs[i][2]);
    }
    for (int i = 0; i < q; ++i) cout << sol[i] << "\n";
}

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