Submission #924637

#TimeUsernameProblemLanguageResultExecution timeMemory
924637winter0101New Home (APIO18_new_home)C++17
100 / 100
4895 ms338176 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) const int maxn=3e5+9; const int mx=2e8; const int mn=-1e8; set<int>cord[maxn]; multiset<int>dubi[maxn]; int n,k,q,line; int now=0; struct lne{ int l,r,tim; bool operator < (const lne &p)const { if (l==p.l&&r==p.r)return tim<p.tim; if (l==p.l)return r<p.r; return l<p.l; } }; multiset<lne>temp[maxn]; vector<pii>st[maxn*4]; void update(int id,int l,int r,int u,int v,const pii &x){ if (l>v||r<u||u>v)return; if (u<=l&&r<=v){ st[id].pb(x); return; } int mid=(l+r)>>1; update(id<<1,l,mid,u,v,x); update(id<<1|1,mid+1,r,u,v,x); } void add_line(int l,int r,int type,int tme){ temp[type].insert({l,r,tme}); } void del_line(int l,int r,int type,int del){ auto it=temp[type].lower_bound({l,r,0}); auto tmp=(*it); update(1,1,line,tmp.tim,del-1,{tmp.l,tmp.r}); temp[type].erase(it); } void add_point(int x,int type,int tme){ if (cord[type].empty())now++; if (cord[type].find(x)!=cord[type].end()){ dubi[type].insert(x); return; } if (cord[type].empty()){ cord[type].insert(x); add_line(mn,x,type,tme); add_line(x,mx,type,tme); return; } auto it=cord[type].upper_bound(x); if (it==cord[type].end()){ it--; del_line((*it),mx,type,tme); add_line(x,mx,type,tme); add_line((*it),x,type,tme); cord[type].insert(x); return; } if (it==cord[type].begin()){ del_line(mn,(*it),type,tme); add_line(x,(*it),type,tme); add_line(mn,x,type,tme); cord[type].insert(x); return; } int l1,r1=(*it); it--; l1=(*it); del_line(l1,r1,type,tme); add_line(x,r1,type,tme); add_line(l1,x,type,tme); cord[type].insert(x); return; } void del_point(int x,int type,int tme){ if (dubi[type].find(x)!=dubi[type].end()){ dubi[type].erase(dubi[type].find(x)); return; } if (sz(cord[type])==1)now--; cord[type].erase(x); if (cord[type].empty()){ del_line(mn,x,type,tme); del_line(x,mx,type,tme); return; } auto it=cord[type].upper_bound(x); if (it==cord[type].end()){ it--; del_line((*it),x,type,tme); del_line(x,mx,type,tme); add_line((*it),mx,type,tme); return; } if (it==cord[type].begin()){ del_line(mn,x,type,tme); del_line(x,(*it),type,tme); add_line(mn,(*it),type,tme); return; } int l1,r1=(*it); it--; l1=(*it); del_line(l1,x,type,tme); del_line(x,r1,type,tme); add_line(l1,r1,type,tme); return; } struct store{ int x,t,a,b; }a[maxn]; pii b[maxn]; vector<int>add[maxn*3],del[maxn*3]; vector<int>answer[maxn*3]; int st1[maxn*4],st2[maxn*4],c[maxn]; /* 1 for a-x 2 for x-a */ void build(int id,int l,int r){ st1[id]=mx,st2[id]=mn; if (l==r)return; int mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); } void upd1(int id,int l,int r,int u,int v,int val){ if (l>v||r<u||u>v)return; if (u<=l&&r<=v){ st1[id]=min(st1[id],val); return; } int mid=(l+r)>>1; upd1(id<<1,l,mid,u,v,val); upd1(id<<1|1,mid+1,r,u,v,val); } void upd2(int id,int l,int r,int u,int v,int val){ if (l>v||r<u||u>v)return; if (u<=l&&r<=v){ st2[id]=max(st2[id],val); return; } int mid=(l+r)>>1; upd2(id<<1,l,mid,u,v,val); upd2(id<<1|1,mid+1,r,u,v,val); } pii get(int id,int l,int r,int u){ pii xxx={mx,mn}; while (true){ xxx.fi=min(xxx.fi,st1[id]); xxx.se=max(xxx.se,st2[id]); if (l==r)break; int mid=(l+r)>>1; if (mid>=u){ id=(id<<1); r=mid; } else { id=(id<<1|1); l=mid+1; } } return xxx; } void new_home(int id,int l,int r){ if (!st[id].empty()){ vector<int>cc; for1(i,l,r){ for (auto v:answer[i]){ if (c[v]==-1)continue; cc.pb(b[v].fi); } } sort(all(cc)); cc.resize(distance(cc.begin(),unique(all(cc)))); if (!cc.empty()){ int m=sz(cc); build(1,1,m); for(auto v:st[id]){ int l1=v.fi,r1=v.se,mid=(l1+r1)/2; l1=lower_bound(all(cc),l1)-cc.begin()+1; r1=upper_bound(all(cc),r1)-cc.begin(); mid=upper_bound(all(cc),mid)-cc.begin(); upd1(1,1,m,l1,mid,v.fi); upd2(1,1,m,mid+1,r1,v.se); } for1(i,l,r){ for (auto v:answer[i]){ if (c[v]==-1)continue; int pos=lower_bound(all(cc),b[v].fi)-cc.begin()+1; pii xxx=get(1,1,m,pos); c[v]=max({c[v],b[v].fi-xxx.fi,xxx.se-b[v].fi}); } } } } if (l==r)return; int mid=(l+r)>>1; new_home(id<<1,l,mid); new_home(id<<1|1,mid+1,r); } void init(){ cin>>n>>k>>q; for1(i,1,n)cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b; for1(i,1,q)cin>>b[i].fi>>b[i].se; } void nentime(){ vector<int>tme; for1(i,1,q){ tme.pb(b[i].se); } sort(all(tme)); tme.resize(distance(tme.begin(),unique(all(tme)))); for1(i,1,n){ a[i].a=lower_bound(all(tme),a[i].a)-tme.begin()+1,a[i].b=upper_bound(all(tme),a[i].b)-tme.begin(); if (a[i].a>a[i].b)continue; add[a[i].a].pb(i); del[a[i].b].pb(i); } for1(i,1,q){ b[i].se=lower_bound(all(tme),b[i].se)-tme.begin()+1; answer[b[i].se].pb(i); } line=sz(tme); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); init(); nentime(); for1(i,1,line){ for (auto v:add[i]){ add_point(a[v].x,a[v].t,i); } for (auto v:answer[i]){ if (now<k){ c[v]=-1; continue; } } for (auto v:del[i]){ del_point(a[v].x,a[v].t,i+1); } } for1(i,1,k){ for (auto u:temp[i]){ update(1,1,line,u.tim,line,{u.l,u.r}); } } new_home(1,1,line); for1(i,1,q)cout<<c[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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...