oj.uz

Submission #852162

# Submission time Handle Problem Language Result Execution time Memory
852162 2023-09-21T10:57:06 Z TS_2392 Examination (JOI19_examination) C++14
100 / 100
 443 ms 138868 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 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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8696 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12872 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 5 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 5 ms 12888 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 6 ms 12892 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Correct 5 ms 12896 KB Output is correct
17 Correct 5 ms 12888 KB Output is correct
18 Correct 4 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 136276 KB Output is correct
2 Correct 280 ms 136280 KB Output is correct
3 Correct 270 ms 136172 KB Output is correct
4 Correct 266 ms 135508 KB Output is correct
5 Correct 257 ms 135600 KB Output is correct
6 Correct 242 ms 134948 KB Output is correct
7 Correct 277 ms 136288 KB Output is correct
8 Correct 272 ms 136264 KB Output is correct
9 Correct 304 ms 136160 KB Output is correct
10 Correct 244 ms 135348 KB Output is correct
11 Correct 242 ms 135356 KB Output is correct
12 Correct 210 ms 134336 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 136276 KB Output is correct
2 Correct 280 ms 136280 KB Output is correct
3 Correct 270 ms 136172 KB Output is correct
4 Correct 266 ms 135508 KB Output is correct
5 Correct 257 ms 135600 KB Output is correct
6 Correct 242 ms 134948 KB Output is correct
7 Correct 277 ms 136288 KB Output is correct
8 Correct 272 ms 136264 KB Output is correct
9 Correct 304 ms 136160 KB Output is correct
10 Correct 244 ms 135348 KB Output is correct
11 Correct 242 ms 135356 KB Output is correct
12 Correct 210 ms 134336 KB Output is correct
13 Correct 333 ms 136828 KB Output is correct
14 Correct 412 ms 136748 KB Output is correct
15 Correct 278 ms 136408 KB Output is correct
16 Correct 304 ms 135872 KB Output is correct
17 Correct 324 ms 136008 KB Output is correct
18 Correct 321 ms 134880 KB Output is correct
19 Correct 393 ms 136636 KB Output is correct
20 Correct 376 ms 136688 KB Output is correct
21 Correct 327 ms 136776 KB Output is correct
22 Correct 240 ms 135580 KB Output is correct
23 Correct 242 ms 135332 KB Output is correct
24 Correct 212 ms 134324 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8696 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12872 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 5 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 5 ms 12888 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 6 ms 12892 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Correct 5 ms 12896 KB Output is correct
17 Correct 5 ms 12888 KB Output is correct
18 Correct 4 ms 12636 KB Output is correct
19 Correct 297 ms 136276 KB Output is correct
20 Correct 280 ms 136280 KB Output is correct
21 Correct 270 ms 136172 KB Output is correct
22 Correct 266 ms 135508 KB Output is correct
23 Correct 257 ms 135600 KB Output is correct
24 Correct 242 ms 134948 KB Output is correct
25 Correct 277 ms 136288 KB Output is correct
26 Correct 272 ms 136264 KB Output is correct
27 Correct 304 ms 136160 KB Output is correct
28 Correct 244 ms 135348 KB Output is correct
29 Correct 242 ms 135356 KB Output is correct
30 Correct 210 ms 134336 KB Output is correct
31 Correct 333 ms 136828 KB Output is correct
32 Correct 412 ms 136748 KB Output is correct
33 Correct 278 ms 136408 KB Output is correct
34 Correct 304 ms 135872 KB Output is correct
35 Correct 324 ms 136008 KB Output is correct
36 Correct 321 ms 134880 KB Output is correct
37 Correct 393 ms 136636 KB Output is correct
38 Correct 376 ms 136688 KB Output is correct
39 Correct 327 ms 136776 KB Output is correct
40 Correct 240 ms 135580 KB Output is correct
41 Correct 242 ms 135332 KB Output is correct
42 Correct 212 ms 134324 KB Output is correct
43 Correct 356 ms 138868 KB Output is correct
44 Correct 353 ms 138760 KB Output is correct
45 Correct 443 ms 138700 KB Output is correct
46 Correct 309 ms 137164 KB Output is correct
47 Correct 323 ms 137236 KB Output is correct
48 Correct 228 ms 134692 KB Output is correct
49 Correct 398 ms 138684 KB Output is correct
50 Correct 357 ms 138656 KB Output is correct
51 Correct 388 ms 138500 KB Output is correct
52 Correct 288 ms 136896 KB Output is correct
53 Correct 246 ms 136272 KB Output is correct