Submission #1212287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212287		nrg_studio	Examination (JOI19_examination)	C++20	100 / 100	1417 ms	17864 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAX_N = 1e5, B = 1000;
struct Student {
    int a, b, id;
    bool operator<(const Student& o) const {return a<o.a;}
};
struct Query {
    int a, b, c, id;
    bool operator<(const Query& o) const {return c>o.c;}
};

Student st[MAX_N], st2[MAX_N];
int mn[MAX_N];

Query qry[MAX_N];
int ans[MAX_N] = {0};
ordered_set<int> sets[MAX_N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, q; cin >> n >> q;

    for (int i=0;i<n;i++) {cin >> st[i].a >> st[i].b;}
    sort(st,st+n);
    for (int i=0;i<n;i++) {st[i].id = i/B;}
    for (int i=0;i<(n+B-1)/B;i++) {mn[i] = st[i*B].a;}
    copy(st,st+n,st2);

    sort(st,st+n,[&](const Student& x, const Student& y) {return x.a+x.b>y.a+y.b;});
    for (int i=0;i<q;i++) {cin >> qry[i].a >> qry[i].b >> qry[i].c; qry[i].id = i;}
    sort(qry,qry+q);

    for (int i=0,p=0;i<q;i++) {
        while (p<n && st[p].a+st[p].b>=qry[i].c) {
            sets[st[p].id].insert(st[p].b);
            p++;
        }
        for (int j=(n+B-1)/B-1;j>=0;j--) {
            if (mn[j]<qry[i].a) {
                for (int k=j*B;k<min(j*B+B,n);k++) {
                    ans[qry[i].id] += (st2[k].a+st2[k].b>=qry[i].c && st2[k].a>=qry[i].a && st2[k].b>=qry[i].b);
                } break;
            } else {ans[qry[i].id] += sets[j].size()-sets[j].order_of_key(qry[i].b);}
        }
    }
    for (int i=0;i<q;i++) {cout << ans[i] << '\n';}
}

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