oj.uz

Submission #239615

# Submission time Handle Problem Language Result Execution time Memory
239615 2020-06-16T20:49:21 Z aggu_01000101 Examination (JOI19_examination) C++14
2 / 100
 3000 ms 286092 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[4*N];
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, int toins){
    if(l>=ll && u<=ll){
        sz[i]++;
        seg[i].insert({toins, freq[i][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, freq[i][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);
            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 47 ms 56696 KB Output is correct
2 Correct 47 ms 56824 KB Output is correct
3 Correct 46 ms 56696 KB Output is correct
4 Correct 46 ms 56704 KB Output is correct
5 Correct 47 ms 56696 KB Output is correct
6 Correct 47 ms 56704 KB Output is correct
7 Correct 83 ms 61944 KB Output is correct
8 Correct 77 ms 62072 KB Output is correct
9 Correct 79 ms 61944 KB Output is correct
10 Correct 73 ms 61948 KB Output is correct
11 Correct 66 ms 60408 KB Output is correct
12 Correct 65 ms 60280 KB Output is correct
13 Correct 76 ms 61944 KB Output is correct
14 Correct 76 ms 61944 KB Output is correct
15 Correct 76 ms 61944 KB Output is correct
16 Correct 65 ms 59896 KB Output is correct
17 Correct 76 ms 61944 KB Output is correct
18 Correct 58 ms 59896 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 286092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 286092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 56696 KB Output is correct
2 Correct 47 ms 56824 KB Output is correct
3 Correct 46 ms 56696 KB Output is correct
4 Correct 46 ms 56704 KB Output is correct
5 Correct 47 ms 56696 KB Output is correct
6 Correct 47 ms 56704 KB Output is correct
7 Correct 83 ms 61944 KB Output is correct
8 Correct 77 ms 62072 KB Output is correct
9 Correct 79 ms 61944 KB Output is correct
10 Correct 73 ms 61948 KB Output is correct
11 Correct 66 ms 60408 KB Output is correct
12 Correct 65 ms 60280 KB Output is correct
13 Correct 76 ms 61944 KB Output is correct
14 Correct 76 ms 61944 KB Output is correct
15 Correct 76 ms 61944 KB Output is correct
16 Correct 65 ms 59896 KB Output is correct
17 Correct 76 ms 61944 KB Output is correct
18 Correct 58 ms 59896 KB Output is correct
19 Execution timed out 3085 ms 286092 KB Time limit exceeded
20 Halted 0 ms 0 KB -