oj.uz

Submission #852092

# Submission time Handle Problem Language Result Execution time Memory
852092 2023-09-21T08:23:42 Z TS_2392 Examination (JOI19_examination) C++14
0 / 100
 303 ms 133880 KB 
#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 l, int r, int idx){
    int len = r - l + 1;
    for(int i = 1, j = l; j <= r; ++i, ++j){
        a[i] = student[j];
    }
    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){
        mark[i] = suf[i] = 0; a[i] = {a[i].se, i};
    }
    suf[len + 1] = 0;
    sort(a + 1, a + 1 + len, [&](const pii &x, const pii &y){
        return x.fi > y.fi;
    });
    for(int j = 1, i = q; i >= 1; --i){
        while(j <= n && 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 idx = 0, i = 1; i <= n; i += Bz, idx += 1){
        preprocess(i, min(n, i + Bz - 1), idx);
    }
    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, 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 6 ms 12816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 133880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 133880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 6 ms 12816 KB Output isn't correct
8 Halted 0 ms 0 KB -