Submission #203838

#TimeUsernameProblemLanguageResultExecution timeMemory
203838SegtreeNew Home (APIO18_new_home)C++14
100 / 100
4485 ms141968 KiB
#include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define N 600010 ll dat[2*N]; void init(){ rep(i,2*N)dat[i]=-1e17; } void upd(ll i,ll x){ i+=N,dat[i]=x; for(;i;i>>=1)dat[i/2]=max(dat[i],dat[i^1]); } ll qry(ll l,ll r){ l+=N,r+=N; ll res=-1e17; for(ll a=l,b=r;a<b;a>>=1,b>>=1){ if(a&1)chmax(res,dat[a++]); if(b&1)chmax(res,dat[--b]); } return res; } struct st{ ll tim,typ,c,d; bool operator<(const st&key)const{ if(this->tim==key.tim){ return this->typ<key.typ; } return this->tim<key.tim; } }; ll n,q,k,x[N],t[N],a[N],b[N],fans[N]; multiset<ll> s[N]; int main(){ cin.tie(0); ios::sync_with_stdio(0); cin>>n>>k>>q; vector<pair<ll,ll> > xs; rep(i,n){ cin>>x[i]>>t[i]>>a[i]>>b[i]; t[i]--; xs.push_back(make_pair(x[i],i)); } sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); vector<st> v; rep(i,n){ pair<ll,ll> key=make_pair(x[i],i); x[i]=lower_bound(xs.begin(),xs.end(),key)-xs.begin(); v.push_back((struct st){a[i],0,x[i]+k,t[i]}); v.push_back((struct st){b[i],2,x[i]+k,t[i]}); } rep(i,q){ ll l,y; cin>>l>>y; v.push_back((struct st){y,1,l,i}); } sort(v.begin(),v.end()); init(); rep(i,k){ s[i].insert(i); s[i].insert(1e17); upd(i,1e17); } for(auto e:v){ if(e.typ==0){ ll place=e.c,col=e.d; auto it=s[col].upper_bound(place); ll r=*it; it--; ll l=*it; upd(l,place); upd(place,r); s[col].insert(place); } if(e.typ==1){ ll place=e.c,id=e.d; ll L=-1,R=1e9,mid; while(L<R-1){ mid=(L+R)>>1; pair<ll,ll> key; key=make_pair(place-mid,-1e17); ll l=lower_bound(xs.begin(),xs.end(),key)-xs.begin()+k; key=make_pair(place+mid,+1e17); ll r=upper_bound(xs.begin(),xs.end(),key)-xs.begin()-1+k; if(qry(0,l)<=r)R=mid; else L=mid; } if(R==1e9)R=-1; fans[id]=R; } if(e.typ==2){ ll place=e.c,col=e.d; s[col].erase(s[col].find(place)); auto it=s[col].upper_bound(place); ll r=*it; it--; ll l=*it; upd(place,-1e17); upd(l,r); } } rep(i,q)cout<<fans[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...