Submission #1230314

#TimeUsernameProblemLanguageResultExecution timeMemory
1230314vivkostovExamination (JOI19_examination)C++20
0 / 100
117 ms8316 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct stu { long long int a,b; }; bool cmp(stu a1,stu a2) { if(a1.a<a2.a)return false; if(a1.a>a2.a)return true; if(a1.b<a2.b)return false; return true; } struct cell { long long int x,y,z,ind; }; bool cmp2(cell a1,cell a2) { if(a1.x<a2.x)return false; if(a1.x>a2.x)return true; return a1.ind<a2.ind; } struct node { int l,r,st; }; int n,q,br=1,otg[100005]; stu a[100005]; cell b[100005]; node p[10000005]; void check(int h) { if(!p[h].l) { br++; p[h].l=br; br++; p[h].r=br; } } void update(int l,int r,int q,int h) { if(l>q||r<q)return; if(l==r) { p[h].st++; return; } int mid=(l+r)/2; check(h); update(l,mid,q,p[h].l); update(mid+1,r,q,p[h].r); p[h].st=p[p[h].l].st+p[p[h].r].st; } int query(int l,int r,int ql,int qr,int h) { if(l>qr||r<ql)return 0; if(l>=ql&&r<=qr)return p[h].st; int mid=(l+r)/2; check(h); return query(l,mid,ql,qr,p[h].l)+query(mid+1,r,ql,qr,p[h].r); } void resh() { int pos=1,l; for(int i=1;i<=q;i++) { while(pos<=n&&a[pos].a>=b[i].x) { update(1,1e9,a[pos].b,1); pos++; } l=b[i].y; otg[b[i].ind]=query(1,1e9,l,1e9,1); } for(int i=1;i<=q;i++) { cout<<otg[i]<<endl; } } void read() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>a[i].a>>a[i].b; } sort(a+1,a+n+1,cmp); for(int i=1;i<=q;i++) { cin>>b[i].x>>b[i].y>>b[i].z; b[i].ind=i; } sort(b+1,b+q+1,cmp2); resh(); } int main() { speed(); read(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...