Submission #259587

#TimeUsernameProblemLanguageResultExecution timeMemory
259587dvdg6566Santa Claus (RMI19_santa)C++14
0 / 100
880 ms130296 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pi; typedef vector<pi> vpi; #define pb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define ALL(x) x.begin(), x.end() #define SZ(x) (ll)x.size() #define f first #define s second const ll MOD = 1e9+7; const ll INF = 1e9; const ll MAXN = 100010; const ll BSIZ= 800; struct node{ ll s,e,m,v,rp; node *l,*r; node(ll _s,ll _e):s(_s),e(_e){ m=(s+e)/2; rp=0; v=1e9; if(s!=e){l=new node(s,m);r=new node(m+1,e);} } void up(ll x,ll val){ if(s==e){ rp+=val; if(rp)v=s; else v=1e9; return; } if(x<=m)l->up(x,val); else r->up(x,val); v=min(l->v,r->v); } ll ask(ll x,ll y){ if(s==x&&e==y)return v; if(y<=m)return l->ask(x,y); else if(x>m)return r->ask(x,y); else return min(l->ask(x,m),r->ask(m+1,y)); } void reset(){ v=1e9; if(s==e)return; l->reset();r->reset(); } }*root; ll N,T; struct node2{ ll s,e,m,v,lz; node2 *l,*r; node2(ll _s,ll _e):s(_s),e(_e){ m=(s+e)/2;v=0;lz=0; if(s!=e){l=new node2(s,m);r=new node2(m+1,e);} } ll minq(ll x,ll y){ if(s==x&&e==y)return v+lz; if(y<=m)return l->minq(x,y)+lz; else if(x>m)return r->minq(x,y)+lz; else return max(l->minq(x,m),r->minq(m+1,y))+lz; } void up(ll x,ll y,ll val){ if(s==x&&e==y){lz+=val;return;} if(y<=m)l->up(x,y,val); else if(x>m)r->up(x,y,val); else{ l->up(x,m,val);r->up(m+1,y,val); } v=max(l->v+l->lz,r->v+r->lz); } void reset(){ v=lz=0; if(s==e)return; l->reset(); r->reset(); } void db(ll k){ if(s==e){cout<<v+k+lz<<' ';return;} l->db(k+lz); r->db(k+lz); if(s==1&&e==N)cout<<'\n'; } }*root2; ll X[MAXN],H[MAXN],V[MAXN]; ll D[MAXN],S[MAXN],M[MAXN]; ll W[MAXN]; int main(){ cin>>T; while(T--){ cin>>N; root=new node(1,N); root2=new node2(1,N); for(ll i=1;i<=N;++i)cin>>X[i]; for(ll i=1;i<=N;++i)cin>>H[i]; for(ll i=1;i<=N;++i)cin>>V[i]; memset(D,0,sizeof(D)); memset(W,0,sizeof(W)); ll lastz=0; for(ll i=1;i<=N;++i)if(!H[i])lastz=max(lastz,i); for(ll i=1;i<=lastz;++i)D[i]=-1; ll L=0; for(ll i=1;i<=N;++i){ if(!H[i]){ M[i]=1e9; ++L; root->up(V[i],1); // cerr<<"Update "<<V[i]<<' '<<1<<'\n'; }else{ ll val=root->ask(V[i],N); M[i]=val; // cerr<<"Value "<<V[i]<<" match with "<<val<<'\n'; if(val!=1e9){ root->up(val,-1); --L; } } if(L==0&&D[i]==0)W[i]=X[i]; } // for(ll i=1;i<=N;++i)cout<<M[i]<<' ';cout<<'\n'; for(ll EN=1;EN<=lastz;++EN){ if(!H[EN])root2->up(V[EN],N,1); else root2->up(V[EN],N,-1); } ll ST=0; for(ll EN=lastz+1;EN<=N;++EN){ assert(H[EN]); root2->up(V[EN],N,-1); ll k=root2->minq(1,N); // cerr<<"At "<<EN<<" RMQ "<<root2->minq(1,N)<<'\n'; if(k>0){D[EN]=-1;continue;} while(ST+2<=EN){ ++ST; // cerr<<"Trying to move to "<<ST<<'\n'; if(H[ST]==0)continue; else{ ll t=M[ST]; root2->up(V[ST],N,1); if(t!=1e9)root2->up(t,N,-1); ll k=root2->minq(1,N); if(k>0){ root2->up(V[ST],N,-1); if(t!=1e9)root2->up(t,N,1); --ST; break; } } } // cerr<<"Ans "<<ST<<' '<<EN<<'\n'; D[EN]=2*X[EN]-X[ST+1]; } for(ll i=1;i<=N;++i){ if(W[i]!=0)assert(W[i]==D[i]); cout<<D[i]<<' '; } cout<<'\n'; // return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...