oj.uz

Submission #239618

# Submission time Handle Problem Language Result Execution time Memory
239618 2020-06-16T21:17:02 Z aggu_01000101 Examination (JOI19_examination) C++14
100 / 100
 2860 ms 171244 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
const int N = 1e5 + 5;
int sz[4*N];
ordered_set seg[4*N];
map<int, int> freq;
int qquery(int l, int u, int i, int ll, int uu, int alim){
    if(l>=ll && u<=uu){
        int lt = seg[i].order_of_key({alim, 0});
        return (sz[i] - lt);
    }
    if(l>uu || u<ll) return 0;
    return qquery(l, mid(l, u), lchild(i), ll, uu, alim) + qquery(mid(l, u)+1, u, rchild(i), ll, uu, alim);
}
void update(int l, int u, int i, int ll, pair<int, int> toins){
    if(l>=ll && u<=ll){
        sz[i]++;
        seg[i].insert(toins);
        return;
    }
    if(l>ll || u<ll) return;
    update(l, mid(l, u), lchild(i), ll, toins);
    update(mid(l, u)+1, u, rchild(i), ll, toins);
    sz[i]++;
    seg[i].insert(toins);
}
struct query{
    int a, b, z;
};
bool cmp(pair<query, int> &aa, pair<query, int> &bb){
    return aa.first.b < bb.first.b;
}
bool cmp1(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.first.second < b.first.second;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, q;
    cin>>n>>q;
    pair<int, int> zr[n];
    pair<pair<int, int>, int> arr[n];
    for(int i = 0;i<n;i++){
        cin>>arr[i].first.first>>arr[i].first.second;
        arr[i].second = i;
        zr[i] = {arr[i].first.first + arr[i].first.second, i};
    }
    sort(arr, arr+n, cmp1);
    sort(zr, zr+n);
    int mp[n];
    for(int i = 0;i<n;i++){
        mp[zr[i].second] = i;
    }
    pair<query, int> qq[q];
    for(int i = 0;i<q;i++){
        cin>>qq[i].first.a>>qq[i].first.b>>qq[i].first.z;
        qq[i].first.z = max(qq[i].first.z, qq[i].first.a + qq[i].first.b);
        qq[i].second = i;
    }
    sort(qq, qq+q, cmp);
    int ind = n-1;
    int qind = q-1;
    int ans[q];
    while(qind >=0){
        while(ind >= 0 && arr[ind].first.second >= qq[qind].first.b){
            //push arr[ind].first.first into the segtree at index mp[arr[ind].second]
            update(0, n-1, 0, mp[arr[ind].second], {arr[ind].first.first, freq[arr[ind].first.first]++});
            ind--;
        }
        //binary search for the first z that satisfies
        int zind = n;
        int lo = 0;
        int hi = n-1;
        while(lo<=hi){
            int mid = mid(lo, hi);
            if(zr[mid].first >= qq[qind].first.z){
                hi = mid - 1;
                zind = min(zind, mid);
            }
            else lo = mid+1;
        }
        //if(zind<n) range query from zind to n-1, for elements greater that qq[qind].first.a
        ans[qq[qind].second] = 0;
        if(zind<n) ans[qq[qind].second] = qquery(0, n-1, 0, zind, n-1, qq[qind].first.a);
        qind--;
    }
    for(int i = 0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100


10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117
 */

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 37880 KB Output is correct
2 Correct 36 ms 37888 KB Output is correct
3 Correct 39 ms 37876 KB Output is correct
4 Correct 37 ms 37976 KB Output is correct
5 Correct 36 ms 38016 KB Output is correct
6 Correct 36 ms 37888 KB Output is correct
7 Correct 52 ms 40824 KB Output is correct
8 Correct 52 ms 40800 KB Output is correct
9 Correct 55 ms 40824 KB Output is correct
10 Correct 53 ms 40824 KB Output is correct
11 Correct 50 ms 40568 KB Output is correct
12 Correct 49 ms 40568 KB Output is correct
13 Correct 53 ms 40824 KB Output is correct
14 Correct 52 ms 40824 KB Output is correct
15 Correct 51 ms 40824 KB Output is correct
16 Correct 52 ms 40568 KB Output is correct
17 Correct 59 ms 40824 KB Output is correct
18 Correct 52 ms 40696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 164192 KB Output is correct
2 Correct 2558 ms 166736 KB Output is correct
3 Correct 2406 ms 166648 KB Output is correct
4 Correct 1626 ms 165880 KB Output is correct
5 Correct 1146 ms 161784 KB Output is correct
6 Correct 1604 ms 161236 KB Output is correct
7 Correct 2231 ms 166680 KB Output is correct
8 Correct 2754 ms 166472 KB Output is correct
9 Correct 2496 ms 166340 KB Output is correct
10 Correct 983 ms 161524 KB Output is correct
11 Correct 1647 ms 165496 KB Output is correct
12 Correct 810 ms 160632 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 164192 KB Output is correct
2 Correct 2558 ms 166736 KB Output is correct
3 Correct 2406 ms 166648 KB Output is correct
4 Correct 1626 ms 165880 KB Output is correct
5 Correct 1146 ms 161784 KB Output is correct
6 Correct 1604 ms 161236 KB Output is correct
7 Correct 2231 ms 166680 KB Output is correct
8 Correct 2754 ms 166472 KB Output is correct
9 Correct 2496 ms 166340 KB Output is correct
10 Correct 983 ms 161524 KB Output is correct
11 Correct 1647 ms 165496 KB Output is correct
12 Correct 810 ms 160632 KB Output is correct
13 Correct 2593 ms 166984 KB Output is correct
14 Correct 2421 ms 166848 KB Output is correct
15 Correct 2860 ms 166480 KB Output is correct
16 Correct 1570 ms 166284 KB Output is correct
17 Correct 1497 ms 162148 KB Output is correct
18 Correct 1620 ms 161048 KB Output is correct
19 Correct 2623 ms 166956 KB Output is correct
20 Correct 2818 ms 166904 KB Output is correct
21 Correct 2358 ms 166840 KB Output is correct
22 Correct 943 ms 161656 KB Output is correct
23 Correct 1576 ms 165692 KB Output is correct
24 Correct 812 ms 160668 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 37880 KB Output is correct
2 Correct 36 ms 37888 KB Output is correct
3 Correct 39 ms 37876 KB Output is correct
4 Correct 37 ms 37976 KB Output is correct
5 Correct 36 ms 38016 KB Output is correct
6 Correct 36 ms 37888 KB Output is correct
7 Correct 52 ms 40824 KB Output is correct
8 Correct 52 ms 40800 KB Output is correct
9 Correct 55 ms 40824 KB Output is correct
10 Correct 53 ms 40824 KB Output is correct
11 Correct 50 ms 40568 KB Output is correct
12 Correct 49 ms 40568 KB Output is correct
13 Correct 53 ms 40824 KB Output is correct
14 Correct 52 ms 40824 KB Output is correct
15 Correct 51 ms 40824 KB Output is correct
16 Correct 52 ms 40568 KB Output is correct
17 Correct 59 ms 40824 KB Output is correct
18 Correct 52 ms 40696 KB Output is correct
19 Correct 2419 ms 164192 KB Output is correct
20 Correct 2558 ms 166736 KB Output is correct
21 Correct 2406 ms 166648 KB Output is correct
22 Correct 1626 ms 165880 KB Output is correct
23 Correct 1146 ms 161784 KB Output is correct
24 Correct 1604 ms 161236 KB Output is correct
25 Correct 2231 ms 166680 KB Output is correct
26 Correct 2754 ms 166472 KB Output is correct
27 Correct 2496 ms 166340 KB Output is correct
28 Correct 983 ms 161524 KB Output is correct
29 Correct 1647 ms 165496 KB Output is correct
30 Correct 810 ms 160632 KB Output is correct
31 Correct 2593 ms 166984 KB Output is correct
32 Correct 2421 ms 166848 KB Output is correct
33 Correct 2860 ms 166480 KB Output is correct
34 Correct 1570 ms 166284 KB Output is correct
35 Correct 1497 ms 162148 KB Output is correct
36 Correct 1620 ms 161048 KB Output is correct
37 Correct 2623 ms 166956 KB Output is correct
38 Correct 2818 ms 166904 KB Output is correct
39 Correct 2358 ms 166840 KB Output is correct
40 Correct 943 ms 161656 KB Output is correct
41 Correct 1576 ms 165692 KB Output is correct
42 Correct 812 ms 160668 KB Output is correct
43 Correct 2620 ms 171024 KB Output is correct
44 Correct 2789 ms 171128 KB Output is correct
45 Correct 2719 ms 171180 KB Output is correct
46 Correct 1564 ms 169596 KB Output is correct
47 Correct 1436 ms 163280 KB Output is correct
48 Correct 1519 ms 161032 KB Output is correct
49 Correct 2372 ms 171244 KB Output is correct
50 Correct 2810 ms 171244 KB Output is correct
51 Correct 2300 ms 170860 KB Output is correct
52 Correct 1113 ms 163108 KB Output is correct
53 Correct 1544 ms 168704 KB Output is correct