Submission #852162

#	Time	Username	Problem	Language	Result	Execution time	Memory
852162		TS_2392	Examination (JOI19_examination)	C++14	100 / 100	443 ms	138868 KiB

examination

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 3, Q = 1e5 + 3, Bz = 320;
struct query{
    int x, y, z, ind;
} qry[Q], cx_qry[Q], cy_qry[Q];
int n, q, res[Q], mark[N];
int suf[N], pos[N], ans[Bz][Q], num_bl;
pii student[N], a[N];
void preprocess(int idx){
    int l = max(idx * Bz, 1), r = min((idx + 1) * Bz - 1, n);
    int len = r - l + 1;

    for(int i = l; i <= r; ++i){
        a[i - l + 1] = student[i];
    }
    sort(a + 1, a + 1 + len);
    for(int j = 1, i = 1; i <= q; ++i){
        while(j <= len && a[j].fi < cx_qry[i].x) ++j;
        pos[cx_qry[i].ind] = j;
    }
    for(int i = 1; i <= len; ++i){
        a[i] = {a[i].se, i};
        mark[i] = suf[i] = 0;
    }
    suf[len + 1] = 0;
    sort(a + 1, a + 1 + len);

    for(int j = len, i = q; i >= 1; --i){
        while(j >= 1 && a[j].fi >= cy_qry[i].y){
            int r = a[j].se; mark[r] = 1;
            for(int ii = r; ii >= 1; --ii) suf[ii] = suf[ii + 1] + mark[ii];
            --j;
        }
        ans[idx][cy_qry[i].ind] = suf[pos[cy_qry[i].ind]];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> student[i].fi >> student[i].se;

    sort(student + 1, student + 1 + n, [&](const pii &a, const pii &b){
        return a.fi + a.se < b.fi + b.se;
    });
    for(int i = 1; i <= q; ++i){
        cin >> qry[i].x >> qry[i].y >> qry[i].z;
        qry[i].ind = i; cx_qry[i] = cy_qry[i] = qry[i];
    }
    sort(qry + 1, qry + 1 + q, [&](const query &a, const query &b){
        return a.z < b.z;
    });
    sort(cx_qry + 1, cx_qry + 1 + q, [&](const query &a, const query &b){
        return a.x < b.x;
    });
    sort(cy_qry + 1, cy_qry + 1 + q, [&](const query &a, const query &b){
        return a.y < b.y;
    });
    num_bl = n / Bz + 1;
    for(int i = 0; i < num_bl; ++i) preprocess(i);
    for(int l = 1, i = 1; i <= q; ++i){
        while(l <= n && student[l].fi + student[l].se < qry[i].z) ++l;
        if(l > n) break;

        int bl_id = (l + Bz - 1) / Bz;
        int lim_j = min(bl_id * Bz, n + 1);

        for(int j = l; j < lim_j; ++j){
            res[qry[i].ind] += (student[j].fi >= qry[i].x && student[j].se >= qry[i].y);
        }
        for(int j = bl_id; j < num_bl; ++j){
            res[qry[i].ind] += ans[j][qry[i].ind];
        }
    }
    for(int i = 1; i <= q; ++i) cout << res[i] << '\n';
    return 0;
}

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