Submission #920838

#TimeUsernameProblemLanguageResultExecution timeMemory
920838WarinchaiExamination (JOI19_examination)C++14
0 / 100
257 ms23432 KiB
#include<bits/stdc++.h> using namespace std; int n,q; struct point{ int i,x,y,z; point(int id=0,int a=0,int b=0,int c=0){ i=id,x=a,y=b,z=c; } bool operator<(const point &t){ return x==t.x?y<t.y:x<t.x; } }; vector<point>v; int ans[600005]; point temp[600005]; struct fenwick{ int info[600005]; void upd(int id,int val){ for(int i=id;i<=600000;i+=i&-i)info[i]+=val; } int fsum(int id){ int ans=0; for(int i=id;i>0;i-=i&-i){ ans+=info[i]; } return ans; } }fw; void solve(int st,int en){ if(st==en)return; int m=(st+en)/2; solve(st,m); solve(m+1,en); //cerr<<st<<" "<<en<<"\n"; int i=st,j=m+1; int id=st; //cerr<<"in solve work\n"; while(i<=m||j<=en){ if(j>en||(i<=m&&v[i].y>=v[j].y)){ temp[id++]=v[i]; if(v[i].i<=n)fw.upd(v[i].z,1); i++; }else{ temp[id++]=v[j]; ans[v[j].i]+=fw.fsum(600000)-fw.fsum(v[j].z-1); j++; } } //cerr<<"in solve work\n"; for(int i=st;i<=m;i++)if(v[i].i<=n)fw.upd(v[i].z,-1); for(int i=st;i<=en;i++)v[i]=temp[i]; } vector<int>val; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ int a,b; cin>>a>>b; v.push_back(point(i,a,b,a+b)); val.push_back(a); val.push_back(b); val.push_back(a+b); } for(int i=1;i<=q;i++){ int a,b,c; cin>>a>>b>>c; v.push_back(point(n+i,a,b,c)); val.push_back(a); val.push_back(b); val.push_back(c); } sort(val.begin(),val.end()); //for(auto x:val)cerr<<x<<" "; //cerr<<"\n"; for(auto &x:v){ //cerr<<lower_bound(val.begin(),val.end(),x.x)-val.begin()<<"+"<<1<<"\n"; x.x=lower_bound(val.begin(),val.end(),x.x)-val.begin()+1; x.y=lower_bound(val.begin(),val.end(),x.y)-val.begin()+1; x.z=lower_bound(val.begin(),val.end(),x.z)-val.begin()+1; } //cerr<<"work\n"; sort(v.begin(),v.end()); reverse(v.begin(),v.end()); //for(auto x:v)cerr<<x.i<<" "<<x.x<<" "<<x.y<<" "<<x.z<<"\n"; //cerr<<"work\n"; solve(0,v.size()-1); //cerr<<"work\n"; for(int i=n+1;i<=n+q;i++){ cout<<ans[i]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...