#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct{
int*tree,*inds;
int*p,n;
void init(int*P,int*PP,int N){
p=P,n=N;
tree=new int[4*N];
inds=PP;
build(0,n-1,1);
}
int build(int l,int r,int node){
if(l==r){
return tree[node]=p[inds[l]];
}
int mid=(l+r)>>1,child=node<<1;
return tree[node]=max(build(l,mid,child),build(mid+1,r,child|1));
}
int L,R;
int query(int l,int r,int node){
if(r<L||R<l){
return INT_MIN;
}
if(L<=l&&r<=R){
return tree[node];
}
int mid=(l+r)>>1,child=node<<1;
return max(query(l,mid,child),query(mid+1,r,child|1));
}
int query(int l,int r){
L=l,R=r;
return query(0,n-1,1);
}
int P;
int walk(int l,int r,int node){
if(l==r){
return inds[l];
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)return walk(l,mid,child);
int val1=tree[child];
int val2=query(mid+1,min(r,P));
if(val2<val1)return walk(l,mid,child);
return walk(mid+1,r,child|1);
}
int walk(int p){
P=p;
return walk(0,n-1,1);
}
void update(int l,int r,int node){
if(l==r){
tree[node]=INT_MIN;
return;
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
tree[node]=max(tree[child],tree[child|1]);
}
void update(int p){
P=p;
update(0,n-1,1);
}
}st1,st2;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X,X+A);
sort(Y,Y+B);
for(int i=0;i<T;i++){
if((!A||X[A-1]<=W[i])&&(!B||Y[B-1]<=S[i])){
return -1;
}
}
int P1[T];
for(int i=0;i<T;i++)P1[i]=i;
sort(P1,P1+T,[&](int i,int j)->bool {
return W[i]<W[j];
});
int T1[T];
for(int i=0;i<T;i++)T1[P1[i]]=i;
st1.init(S,P1,T);
int can=-1;
multiset<int>ms1;
for(int i=0;i<A;i++){
while(can+1<T&&W[P1[can+1]]<X[i]){
can++;
}
if(can!=-1){
ms1.insert(can);
}
}
int P2[T];
for(int i=0;i<T;i++)P2[i]=i;
sort(P2,P2+T,[&](int i,int j)->bool {
return S[i]<S[j];
});
int T2[T];
for(int i=0;i<T;i++)T2[P2[i]]=i;
st2.init(W,P2,T);
can=-1;
multiset<int>ms2;
for(int i=0;i<B;i++){
while(can+1<T&&S[P2[can+1]]<Y[i]){
can++;
}
if(can!=-1){
ms2.insert(can);
}
}
bool died[T];
memset(died,0,T);
int left=T,turn=0;
while(left){
turn++;
vector<int>torem;
for(int i:ms1){
//cerr<<i<<" :: ";
int val=st1.walk(i);
if(died[val]){
//cerr<<"failed\n";
torem.push_back(i);
}else{
//cerr<<"killed "<<val<<" { "<<T1[val]<<" "<<T2[val]<<" }\n";
died[val]=1;
st1.update(T1[val]);
st2.update(T2[val]);
left--;
}
}
for(int i:torem){
ms1.erase(i);
}
//cerr<<"\n";
torem.clear();
for(int i:ms2){
//cerr<<i<<" :: ";
int val=st2.walk(i);
if(died[val]){
//cerr<<"failed\n";
torem.push_back(i);
}else{
//cerr<<"killed "<<val<<" { "<<T1[val]<<" "<<T2[val]<<" }\n";
died[val]=1;
st1.update(T1[val]);
st2.update(T2[val]);
left--;
}
}
for(int i:torem){
ms2.erase(i);
}
//cerr<<"\n-----------------\n";
}
return turn;
}
