제출 #490106

#제출 시각아이디문제언어결과실행 시간메모리
490106cfalasExamination (JOI19_examination)C++17
0 / 100
330 ms3452 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define FORi(i,a,b) for(ll i=((ll)a);i<(ll)b;i++) #define FOR(i,n) FORi(i,0,n) #define INF 120 #define MID ((l+r)/2) typedef pair<int, int> ii; #define F first #define S second struct seg{ seg* L=NULL, *R=NULL; int val=0; void update(int x, int l=0, int r=INF){ if(l==r && l==x) val++; else if(l==r) return; else{ if(x<=MID){ if(!L) L = new seg; L->update(x,l,MID); } else{ if(!R) R = new seg; R->update(x,MID+1,r); } val = 0; if(L) val+=L->val; if(R) val+=R->val; } } int query(int rl, int rr, int l=0, int r=INF){ if(rl<=l && r<=rr) return val; else if(rr<l || r<rl) return 0; else{ int ans=0; if(L) ans+=L->query(rl,rr,l,MID); if(R) ans+=R->query(rl,rr,MID+1,r); return ans; } } }; struct seg2{ seg2* L=NULL, *R=NULL; seg val; void update(ii x, int l=0, int r=INF){ if(l==r && l==x.F) val.update(x.S); else if(l==r) return; else{ if(x.F<=MID){ if(!L) L = new seg2; L->update(x,l,MID); } else{ if(!R) R = new seg2; R->update(x,MID+1,r); } val.update(x.S); } } int query(ii rl, ii rr, int l=0, int r=INF){ if(rl.F<=l && r<=rr.F) return val.query(rl.S, rr.S); else if(rr.F<l || r<rl.F) return 0; else{ int ans=0; if(L) ans+=L->query(rl,rr,l,MID); if(R) ans+=R->query(rl,rr,MID+1,r); return ans; } } }; struct seg3{ seg3* L=NULL, *R=NULL; seg2 val; void update(pair<ii,int> x, int l=0, int r=2*INF){ if(l==r && l==x.S) val.update(x.F); else if(l==r) return; else{ if(x.S<=MID){ if(!L) L = new seg3; L->update(x,l,MID); } else{ if(!R) R = new seg3; R->update(x,MID+1,r); } val.update(x.F); } } int query(pair<ii,int> rl, pair<ii,int> rr, int l=0, int r=2*INF){ if(rl.S<=l && r<=rr.S) return val.query(rl.F, rr.F); else if(rr.S<l || r<rl.S) return 0; else{ int ans=0; if(L) ans+=L->query(rl,rr,l,MID); if(R) ans+=R->query(rl,rr,MID+1,r); return ans; } } }; int main(){ int n, q; cin>>n>>q; seg3 s; FOR(i,n){ int a, b; cin>>a>>b; s.update({{a,b}, a+b}); } while(q--){ int a, b, c; cin>>a>>b>>c; cout<<s.query({{a,b},c}, {{INF, INF}, 2*INF})<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...