#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{
int s,e,m,v,rp;
node *l,*r;
node(int _s,int _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(int x,int 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);
}
int ask(int x,int 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;
int N,T;
struct node2{
int s,e,m,v,lz;
node2 *l,*r;
node2(int _s,int _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);}
}
int minq(int x,int 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(int x,int y,int 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(int 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;
int X[MAXN],H[MAXN],V[MAXN];
int D[MAXN],S[MAXN],M[MAXN];
set<int> A; // children to accept
set<int> B; // presents to clear
int main(){
cin>>T;
while(T--){
cin>>N;
root=new node(1,N);
root2=new node2(1,N);
for(int i=1;i<=N;++i)cin>>X[i];
for(int i=1;i<=N;++i)cin>>H[i];
for(int i=1;i<=N;++i)cin>>V[i];
memset(D,0,sizeof(D));
int lastz=0;
for(int i=1;i<=N;++i)if(!H[i])lastz=max(lastz,i);
for(int i=1;i<=lastz;++i)D[i]=-1;
int L=0;
for(int i=1;i<=N;++i){
if(!H[i]){
M[i]=1e9;
++L;
root->up(V[i],1);
// cerr<<"Update "<<V[i]<<' '<<1<<'\n';
}else{
int 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)D[i]=X[i];
}
// for(int i=1;i<=N;++i)cout<<M[i]<<' ';cout<<'\n';
for(int EN=1;EN<=lastz;++EN){
if(!H[EN])root2->up(V[EN],N,1);
else root2->up(V[EN],N,-1);
}
int ST=0;
for(int EN=lastz+1;EN<=N;++EN){
assert(H[EN]);
root2->up(V[EN],N,-1);
int 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{
int t=M[ST];
// cerr<<"Trading "<<V[ST]<<" removing "<<t<<'\n';
root2->up(V[ST],N,1);
if(t!=1e9)root2->up(t,N,-1);
int k=root2->minq(1,N);
if(k>0){
// cerr<<"Fail\n";
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(int i=1;i<=N;++i){
cout<<D[i]<<' ';
}
cout<<'\n';
// return 0;
}
}
Compilation message
santa.cpp: In member function 'void node2::up(int, int, int)':
santa.cpp:69:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if(s==x&e==y){lz+=val;return;}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
1024 KB |
Output isn't correct |
| 3 |
Incorrect |
19 ms |
3200 KB |
Output isn't correct |
| 4 |
Incorrect |
45 ms |
6648 KB |
Output isn't correct |
| 5 |
Incorrect |
101 ms |
13560 KB |
Output isn't correct |
| 6 |
Incorrect |
164 ms |
21404 KB |
Output isn't correct |
| 7 |
Incorrect |
302 ms |
37624 KB |
Output isn't correct |
| 8 |
Incorrect |
503 ms |
57336 KB |
Output isn't correct |
| 9 |
Incorrect |
609 ms |
70936 KB |
Output isn't correct |
| 10 |
Incorrect |
862 ms |
101812 KB |
Output isn't correct |
