oj.uz

Submission #297945

# Submission time Handle Problem Language Result Execution time Memory
297945 2020-09-12T08:09:23 Z b00n0rp Examination (JOI19_examination) C++17
100 / 100
 2812 ms 184336 KB 
#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pii pair<int,int>
#define F first
#define S second

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int MX = 200005;

int n,q;

pair<pii,pii> a[MX],quer[MX];
int ans[MX];

indexed_set seg[2*MX];

int SZ = 0;

void upd(int pos,pii val){
    pos += SZ;
    while(pos){
        seg[pos].insert(val);
        pos /= 2;
    }
}

int query(int l,int val){
    l += SZ;
    int r = 2*SZ;
    int res = 0;
    while(l < r){
        if(l%2){
            res += seg[l].size()-seg[l].order_of_key({val,-1});
            l++;
        }
        if(r%2){
            --r;
            res += seg[r].size()-seg[r].order_of_key({val,-1});
        }
        l /= 2;
        r /= 2;
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    
    set<int> s;
    map<int,int> m;

    REP(i,n){
        cin >> a[i].S.F >> a[i].S.S;
        a[i].F.F = a[i].S.F+a[i].S.S;
        a[i].F.S = i;
        s.insert(a[i].S.F);
    }
    sort(a,a+n);
    REP(i,q){
        cin >> quer[i].S.F >> quer[i].S.S >> quer[i].F.F;
        quer[i].F.F = max(quer[i].F.F,quer[i].S.F+quer[i].S.S);
        s.insert(quer[i].S.F);
        quer[i].F.S = i;
    }
    sort(quer,quer+q);
    
    for(auto x:s){
        m[x] = SZ++;
    }
    REP(i,n) a[i].S.F = m[a[i].S.F];
    REP(i,q) quer[i].S.F = m[quer[i].S.F];
    int ind = n-1;
    for(int i = q-1; i >= 0; i --){
        while(ind >= 0 and a[ind].F.F >= quer[i].F.F){
            upd(a[ind].S.F,{a[ind].S.S,a[ind].F.S});
            ind--;
        }
        ans[quer[i].F.S] = query(quer[i].S.F,quer[i].S.S);
    }
    REP(i,q) cout << ans[i] << "\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37880 KB Output is correct
2 Correct 37 ms 37888 KB Output is correct
3 Correct 37 ms 37880 KB Output is correct
4 Correct 38 ms 37904 KB Output is correct
5 Correct 44 ms 37880 KB Output is correct
6 Correct 37 ms 37880 KB Output is correct
7 Correct 55 ms 41208 KB Output is correct
8 Correct 56 ms 41196 KB Output is correct
9 Correct 55 ms 41084 KB Output is correct
10 Correct 55 ms 41196 KB Output is correct
11 Correct 43 ms 38904 KB Output is correct
12 Correct 44 ms 38904 KB Output is correct
13 Correct 58 ms 41208 KB Output is correct
14 Correct 60 ms 41336 KB Output is correct
15 Correct 55 ms 41208 KB Output is correct
16 Correct 42 ms 38392 KB Output is correct
17 Correct 53 ms 41080 KB Output is correct
18 Correct 41 ms 38648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2460 ms 159624 KB Output is correct
2 Correct 2435 ms 159704 KB Output is correct
3 Correct 2440 ms 159608 KB Output is correct
4 Correct 1364 ms 159608 KB Output is correct
5 Correct 410 ms 70600 KB Output is correct
6 Correct 392 ms 70520 KB Output is correct
7 Correct 2245 ms 154932 KB Output is correct
8 Correct 2412 ms 159792 KB Output is correct
9 Correct 2076 ms 155384 KB Output is correct
10 Correct 294 ms 54392 KB Output is correct
11 Correct 1155 ms 159480 KB Output is correct
12 Correct 328 ms 60536 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2460 ms 159624 KB Output is correct
2 Correct 2435 ms 159704 KB Output is correct
3 Correct 2440 ms 159608 KB Output is correct
4 Correct 1364 ms 159608 KB Output is correct
5 Correct 410 ms 70600 KB Output is correct
6 Correct 392 ms 70520 KB Output is correct
7 Correct 2245 ms 154932 KB Output is correct
8 Correct 2412 ms 159792 KB Output is correct
9 Correct 2076 ms 155384 KB Output is correct
10 Correct 294 ms 54392 KB Output is correct
11 Correct 1155 ms 159480 KB Output is correct
12 Correct 328 ms 60536 KB Output is correct
13 Correct 2405 ms 159696 KB Output is correct
14 Correct 2642 ms 159872 KB Output is correct
15 Correct 2567 ms 159864 KB Output is correct
16 Correct 1389 ms 159508 KB Output is correct
17 Correct 402 ms 70288 KB Output is correct
18 Correct 388 ms 70520 KB Output is correct
19 Correct 2264 ms 159616 KB Output is correct
20 Correct 2353 ms 159812 KB Output is correct
21 Correct 2305 ms 158840 KB Output is correct
22 Correct 293 ms 54428 KB Output is correct
23 Correct 1242 ms 159608 KB Output is correct
24 Correct 333 ms 60680 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37880 KB Output is correct
2 Correct 37 ms 37888 KB Output is correct
3 Correct 37 ms 37880 KB Output is correct
4 Correct 38 ms 37904 KB Output is correct
5 Correct 44 ms 37880 KB Output is correct
6 Correct 37 ms 37880 KB Output is correct
7 Correct 55 ms 41208 KB Output is correct
8 Correct 56 ms 41196 KB Output is correct
9 Correct 55 ms 41084 KB Output is correct
10 Correct 55 ms 41196 KB Output is correct
11 Correct 43 ms 38904 KB Output is correct
12 Correct 44 ms 38904 KB Output is correct
13 Correct 58 ms 41208 KB Output is correct
14 Correct 60 ms 41336 KB Output is correct
15 Correct 55 ms 41208 KB Output is correct
16 Correct 42 ms 38392 KB Output is correct
17 Correct 53 ms 41080 KB Output is correct
18 Correct 41 ms 38648 KB Output is correct
19 Correct 2460 ms 159624 KB Output is correct
20 Correct 2435 ms 159704 KB Output is correct
21 Correct 2440 ms 159608 KB Output is correct
22 Correct 1364 ms 159608 KB Output is correct
23 Correct 410 ms 70600 KB Output is correct
24 Correct 392 ms 70520 KB Output is correct
25 Correct 2245 ms 154932 KB Output is correct
26 Correct 2412 ms 159792 KB Output is correct
27 Correct 2076 ms 155384 KB Output is correct
28 Correct 294 ms 54392 KB Output is correct
29 Correct 1155 ms 159480 KB Output is correct
30 Correct 328 ms 60536 KB Output is correct
31 Correct 2405 ms 159696 KB Output is correct
32 Correct 2642 ms 159872 KB Output is correct
33 Correct 2567 ms 159864 KB Output is correct
34 Correct 1389 ms 159508 KB Output is correct
35 Correct 402 ms 70288 KB Output is correct
36 Correct 388 ms 70520 KB Output is correct
37 Correct 2264 ms 159616 KB Output is correct
38 Correct 2353 ms 159812 KB Output is correct
39 Correct 2305 ms 158840 KB Output is correct
40 Correct 293 ms 54428 KB Output is correct
41 Correct 1242 ms 159608 KB Output is correct
42 Correct 333 ms 60680 KB Output is correct
43 Correct 2632 ms 177780 KB Output is correct
44 Correct 2524 ms 177724 KB Output is correct
45 Correct 2812 ms 177808 KB Output is correct
46 Correct 1501 ms 180856 KB Output is correct
47 Correct 409 ms 73596 KB Output is correct
48 Correct 362 ms 71416 KB Output is correct
49 Correct 2709 ms 184336 KB Output is correct
50 Correct 2476 ms 182804 KB Output is correct
51 Correct 2679 ms 184104 KB Output is correct
52 Correct 296 ms 57720 KB Output is correct
53 Correct 1304 ms 180344 KB Output is correct