Submission #406141

#TimeUsernameProblemLanguageResultExecution timeMemory
406141kshitij_sodaniNew Home (APIO18_new_home)C++14
0 / 100
5121 ms855556 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' llo n,k,q; llo ans[300001]; set<llo> pre[300001]; map<llo,llo> pre2[300001]; bool vis[3000001]; map<pair<llo,pair<llo,llo>>,llo> xx; map<pair<llo,pair<llo,llo>>,llo> xx2; map<llo,llo> ss; map<llo,llo> ss2; vector<pair<llo,llo>> yy; llo ne=0; llo nn; pair<llo,llo> solve(llo i,llo j){ pair<llo,llo> ac={i,0}; pair<llo,llo> ac2={j+1,0}; return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1}; } set<pair<llo,llo>> tree[4*800001]; //llo ans[300001]; void update(llo no,llo l,llo r,llo aa,llo bb,pair<llo,llo> x,llo st){ /*if(no==0){ cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl; }*/ if(r<aa or l>bb){ return; } if(aa<=l and r<=bb){ //cout<<l<<",,"<<r<<endl; tree[no].insert(x); } else{ llo mid=(l+r)/2; update(no*2+1,l,mid,aa,bb,x,st); update(no*2+2,mid+1,r,aa,bb,x,st); } } llo query(llo no,llo l,llo r,llo i){ llo cur=0; while(tree[no].size()){ if(vis[(*(tree[no].begin())).b]){ tree[no].erase(tree[no].begin()); } else{ break; } } while(tree[no].size()){ auto j=tree[no].end(); j--; if(vis[(*j).b]){ tree[no].erase(j); } else{ break; } } if(tree[no].size()){ //cout<<l<<","<<r<<","<<yy[i].a<<endl; cur=max(cur,abs((*tree[no].begin()).a-yy[i].a)); auto jj=tree[no].end(); jj--; cur=max(cur,abs((*jj).a-yy[i].a)); } if(l<r){ llo mid=(l+r)/2; if(i<=mid){ cur=max(cur,query(no*2+1,l,mid,i)); } else{ cur=max(cur,query(no*2+2,mid+1,r,i)); } } return cur; } void add(llo i,llo aa,llo bb,llo st){ llo mid=(aa+bb)/2; if(st==1){ xx[{i,{aa,mid}}]=ne; pair<llo,llo> ind=solve(aa,mid); update(0,0,nn-1,ind.a,ind.b,{aa,ne},0); ne++; xx[{i,{mid+1,bb}}]=ne; ind=solve(mid+1,bb); update(0,0,nn-1,ind.a,ind.b,{bb,ne},1); ne++; } else{ vis[xx[{i,{aa,mid}}]]=1; vis[xx[{i,{mid+1,bb}}]]=1; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>k>>q; vector<pair<pair<llo,llo>,pair<llo,llo>>> cur; for(llo i=0;i<n;i++){ llo x,aa,bb,tt; cin>>x>>tt>>aa>>bb; ss[x]++; tt--; cur.pb({{aa,-1},{x,tt}}); cur.pb({{bb,1},{x,tt}}); } for(llo i=0;i<q;i++){ llo x,aa; cin>>x>>aa; ss[x]++; cur.pb({{aa,0},{x,i}}); } sort(cur.begin(),cur.end()); llo ind5=-1; ss[-1e9]++; ss[1e9]++; for(auto j:ss){ ind5++; ss2[j.a]=ind5; yy.pb({j.a,ind5}); } nn=yy.size(); //sort(cur.begin(),cur.end()); /* for(auto j:yy){ cout<<j.a<<","; } cout<<endl;*/ for(llo i=0;i<k;i++){ pre[i].insert(-1e9); pre2[i][-1e9]++; pre[i].insert(1e9); pre2[i][1e9]++; add(i,-1e9,1e9,1); // xx[{i,{-1e9,1e9}}]=; // update(0,0,nn-1,0,nn-1); } for(auto j:cur){ if(j.a.b==-1){ //add //continue; if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){ pre2[j.b.b][j.b.a]++; } else{ pre2[j.b.b][j.b.a]++; llo re=*(pre[j.b.b].lower_bound(j.b.a)); auto jj=pre[j.b.b].lower_bound(j.b.a); jj--; llo le=*jj; pre[j.b.b].insert(j.b.a); add(j.b.b,le,re,0); add(j.b.b,le,j.b.a,1); add(j.b.b,j.b.a,re,1); } } else if(j.a.b==1){ //remove //continue; pre2[j.b.b][j.b.a]--; if(pre2[j.b.b][j.b.a]==0){ pre[j.b.b].erase(j.b.a); llo re=*(pre[j.b.b].lower_bound(j.b.a)); auto jj=pre[j.b.b].lower_bound(j.b.a); jj--; llo le=*jj; add(j.b.b,le,j.b.a,0); add(j.b.b,j.b.a,re,0); add(j.b.b,le,re,1); } } else{ //cout<<j.b.a<<":"<<j.b.b<<endl; llo ans2=query(0,0,nn-1,ss2[j.b.a]); if(ans2>1e8){ ans2=-1; } ans[j.b.b]=ans2; } } for(llo i=0;i<q;i++){ cout<<ans[i]<<endl; } /*for(llo i=0;i<cur.size();i++){ cur[i].b.a=ss2[cur[i].b.a]; }*/ 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...