oj.uz

Submission #297944

# Submission time Handle Problem Language Result Execution time Memory
297944 2020-09-12T08:07:19 Z b00n0rp Examination (JOI19_examination) C++17
43 / 100
 3000 ms 182888 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;
        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 38016 KB Output is correct
3 Correct 37 ms 37888 KB Output is correct
4 Correct 37 ms 37880 KB Output is correct
5 Correct 37 ms 37888 KB Output is correct
6 Correct 38 ms 37880 KB Output is correct
7 Correct 56 ms 41208 KB Output is correct
8 Correct 57 ms 41208 KB Output is correct
9 Correct 58 ms 41208 KB Output is correct
10 Correct 55 ms 41208 KB Output is correct
11 Correct 44 ms 38868 KB Output is correct
12 Correct 44 ms 38904 KB Output is correct
13 Correct 57 ms 41208 KB Output is correct
14 Correct 58 ms 41224 KB Output is correct
15 Correct 60 ms 41208 KB Output is correct
16 Correct 41 ms 38392 KB Output is correct
17 Correct 55 ms 41208 KB Output is correct
18 Correct 43 ms 38656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2619 ms 159680 KB Output is correct
2 Correct 2655 ms 159644 KB Output is correct
3 Correct 2640 ms 159608 KB Output is correct
4 Correct 1763 ms 159608 KB Output is correct
5 Correct 552 ms 70520 KB Output is correct
6 Correct 387 ms 70520 KB Output is correct
7 Correct 2499 ms 155000 KB Output is correct
8 Correct 2635 ms 159736 KB Output is correct
9 Correct 2155 ms 155000 KB Output is correct
10 Correct 306 ms 54392 KB Output is correct
11 Correct 1362 ms 159608 KB Output is correct
12 Correct 317 ms 60536 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2619 ms 159680 KB Output is correct
2 Correct 2655 ms 159644 KB Output is correct
3 Correct 2640 ms 159608 KB Output is correct
4 Correct 1763 ms 159608 KB Output is correct
5 Correct 552 ms 70520 KB Output is correct
6 Correct 387 ms 70520 KB Output is correct
7 Correct 2499 ms 155000 KB Output is correct
8 Correct 2635 ms 159736 KB Output is correct
9 Correct 2155 ms 155000 KB Output is correct
10 Correct 306 ms 54392 KB Output is correct
11 Correct 1362 ms 159608 KB Output is correct
12 Correct 317 ms 60536 KB Output is correct
13 Correct 2600 ms 159944 KB Output is correct
14 Correct 2923 ms 159736 KB Output is correct
15 Correct 2804 ms 162296 KB Output is correct
16 Correct 1692 ms 161996 KB Output is correct
17 Correct 498 ms 72568 KB Output is correct
18 Correct 389 ms 71544 KB Output is correct
19 Correct 2439 ms 162552 KB Output is correct
20 Correct 2637 ms 162768 KB Output is correct
21 Correct 2405 ms 161784 KB Output is correct
22 Correct 317 ms 56184 KB Output is correct
23 Correct 1498 ms 161364 KB Output is correct
24 Correct 323 ms 61432 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 37880 KB Output is correct
2 Correct 37 ms 38016 KB Output is correct
3 Correct 37 ms 37888 KB Output is correct
4 Correct 37 ms 37880 KB Output is correct
5 Correct 37 ms 37888 KB Output is correct
6 Correct 38 ms 37880 KB Output is correct
7 Correct 56 ms 41208 KB Output is correct
8 Correct 57 ms 41208 KB Output is correct
9 Correct 58 ms 41208 KB Output is correct
10 Correct 55 ms 41208 KB Output is correct
11 Correct 44 ms 38868 KB Output is correct
12 Correct 44 ms 38904 KB Output is correct
13 Correct 57 ms 41208 KB Output is correct
14 Correct 58 ms 41224 KB Output is correct
15 Correct 60 ms 41208 KB Output is correct
16 Correct 41 ms 38392 KB Output is correct
17 Correct 55 ms 41208 KB Output is correct
18 Correct 43 ms 38656 KB Output is correct
19 Correct 2619 ms 159680 KB Output is correct
20 Correct 2655 ms 159644 KB Output is correct
21 Correct 2640 ms 159608 KB Output is correct
22 Correct 1763 ms 159608 KB Output is correct
23 Correct 552 ms 70520 KB Output is correct
24 Correct 387 ms 70520 KB Output is correct
25 Correct 2499 ms 155000 KB Output is correct
26 Correct 2635 ms 159736 KB Output is correct
27 Correct 2155 ms 155000 KB Output is correct
28 Correct 306 ms 54392 KB Output is correct
29 Correct 1362 ms 159608 KB Output is correct
30 Correct 317 ms 60536 KB Output is correct
31 Correct 2600 ms 159944 KB Output is correct
32 Correct 2923 ms 159736 KB Output is correct
33 Correct 2804 ms 162296 KB Output is correct
34 Correct 1692 ms 161996 KB Output is correct
35 Correct 498 ms 72568 KB Output is correct
36 Correct 389 ms 71544 KB Output is correct
37 Correct 2439 ms 162552 KB Output is correct
38 Correct 2637 ms 162768 KB Output is correct
39 Correct 2405 ms 161784 KB Output is correct
40 Correct 317 ms 56184 KB Output is correct
41 Correct 1498 ms 161364 KB Output is correct
42 Correct 323 ms 61432 KB Output is correct
43 Correct 2801 ms 182888 KB Output is correct
44 Correct 2640 ms 182648 KB Output is correct
45 Execution timed out 3102 ms 182696 KB Time limit exceeded
46 Halted 0 ms 0 KB -