Submission #239618

#TimeUsernameProblemLanguageResultExecution timeMemory
239618aggu_01000101Examination (JOI19_examination)C++14
100 / 100
2860 ms171244 KiB
#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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...