Submission #854686

#TimeUsernameProblemLanguageResultExecution timeMemory
854686DobromirAngelovExamination (JOI19_examination)C++14
0 / 100
208 ms14372 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=1e5+5; const int MAXQ=1e5+5; struct point { int x,y,z,num; }; int n,q; point p[MAXN+MAXQ]; int tree[MAXN+MAXQ]; int ans[MAXQ]; void update(int idx,int val) { while(idx<=n+q) { tree[idx]+=val; idx+=idx&(-idx); } } int query(int idx) { int ret=0; while(idx>0) { ret+=tree[idx]; idx-=idx&(-idx); } return ret; } void cdq(int l,int r) { if(l+1>=r) return; int mid=(l+r)/2; cdq(l,mid); cdq(mid,r); vector<int> hist; vector<point> tmp; int ptr1=l, ptr2=mid; int cntl=0; while(ptr1<mid && ptr2<r) { if(p[ptr1].y>=p[ptr2].y) { if(!p[ptr1].num) { update(p[ptr1].z,1); hist.push_back(p[ptr1].z); cntl++; } tmp.push_back(p[ptr1++]); } else { if(p[ptr2].num) ans[p[ptr2].num]+=cntl-query(p[ptr2].z-1); tmp.push_back(p[ptr2++]); } } while(ptr1<mid) tmp.push_back(p[ptr1++]); while(ptr2<r) { if(p[ptr2].num) ans[p[ptr2].num]+=cntl-query(p[ptr2].z-1); tmp.push_back(p[ptr2++]); } for(int i=0;i<hist.size();i++) update(hist[i], -1); for(int i=l;i<r;i++) p[i]=tmp[i-l]; return; } bool cmpx(point a,point b) {return a.x<b.x;} bool cmpy(point a,point b) {return a.y<b.y;} bool cmpz(point a,point b) {return a.z<b.z;} void compress() { p[0].x=p[0].y=p[0].z=-1; sort(p+1,p+n+q+1,cmpx); int ptr=0; for(int i=1;i<=n+q;i++) { if(p[i].x!=p[i-1].x) ptr++; p[i].x=ptr; } sort(p+1,p+n+q+1,cmpy); ptr=0; for(int i=1;i<=n+q;i++) { if(p[i].y!=p[i-1].y) ptr++; p[i].y=ptr; } sort(p+1,p+n+q+1,cmpz); ptr=0; for(int i=1;i<=n+q;i++) { if(p[i].z!=p[i-1].z) ptr++; p[i].z=ptr; } } bool cmp(point a,point b) { if(a.x==b.x) { if((a.num && b.num) || (!a.num && !b.num)) { if(a.y==b.y) return a.z>b.z; return a.y>b.y; } return a.num<b.num; } return a.x>b.x; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>q; for(int i=1;i<=n;i++) { cin>>p[i].x>>p[i].y; p[i].z=p[i].x+p[i].y; p[i].num=0; } for(int i=n+1;i<=n+q;i++) { cin>>p[i].x>>p[i].y>>p[i].z; p[i].num=i-n; } compress(); sort(p+1,p+n+q+1,cmp); cdq(1,n+q+1); for(int i=1;i<=q;i++) cout<<ans[i]<<endl; return 0; }

Compilation message (stderr)

examination.cpp: In function 'void cdq(int, int)':
examination.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<hist.size();i++) update(hist[i], -1);
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...