#include <bits/stdc++.h>
#include "robots.h"
#define MAX 505000
typedef std::pair<int,int> pii;
typedef std::pair<int,int*> pipo;
typedef std::pair<pii,int> ppi;
bool pego[MAX];
const int inf = 1e9;
struct SegTree {
std::deque<ppi> tab[MAX*4];
void update(int t,ppi k,int la=0,int ra=MAX-1,int pos=1){
tab[pos].push_back(k);
int m = (la+ra)/2;
if(la==ra)return;
if(t<=m)
update(t,k,la,m,pos*2);
else
update(t,k,m+1,ra,(pos*2)+1);
}
void sortar(int la=0,int ra=MAX-1,int pos=1){
std::sort(tab[pos].begin(),tab[pos].end());
int m = (la+ra)/2;
sortar(la,m,pos*2);
sortar(m+1,ra,(pos*2)+1);
}
void limpa(int x){
while(tab[x].size()&&pego[tab[x].front().second])tab[x].pop_front();
}
ppi query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
if(ra<l||la>r)return {{inf,inf},inf};
if(la>=l&&ra<=r){
limpa(pos);
if(tab[pos].size())return tab[pos].front();
return {{inf,inf},inf};
}
int m = (la+ra)/2;
return std::min(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}
};
//SegTree grupoA,grupoB;
int putaway(int A,int B,int T,int _X[],int _Y[],int _W[],int _S[]){
std::vector<int> X,Y,W,S;
for(int i=0;i!=A;++i){
X.push_back(_X[i]);
}
for(int i=0;i!=B;++i){
Y.push_back(_Y[i]);
}
for(int i=0;i!=T;++i){
W.push_back(_W[i]);
S.push_back(_S[i]);
}
{
std::vector<pipo> vec;
for(auto&x:X){
vec.push_back({x,&x});
}
for(auto&x:Y){
vec.push_back({x,&x});
}
for(auto&x:W){
vec.push_back({x,&x});
}
for(auto&x:S){
vec.push_back({x,&x});
}
std::sort(vec.begin(),vec.end());
int cur=2,last=-(1e9);
for(auto&x:vec){
if(x.first!=last){
++cur;
last=x.first;
}
*x.second=cur;
}
}
std::sort(X.begin(),X.end());
std::sort(Y.begin(),Y.end());
int pesos[T]={};
{
std::vector<pii> vec;
///T itens
for(int i=0;i!=T;++i){
vec.push_back({W[i],i});
}
std::sort(vec.begin(),vec.end());
///A robos
int soma[T]={};
int cur=0;
for(int i=0;i!=A;++i){
while(cur!=T&&(vec[cur].first<X[i])){
++cur;
}
if(cur){
soma[cur-1]++;
}
}
int s=0;
for(int i=T-1;i!=-1;--i){
s+=soma[i];
pesos[vec[i].second]+=s;
}
}
{
std::vector<pii> vec;
///T itens
for(int i=0;i!=T;++i){
vec.push_back({S[i],i});
}
std::sort(vec.begin(),vec.end());
///A robos
int soma[T]={};
int cur=0;
for(int i=0;i!=B;++i){
while(cur!=T&&(vec[cur].first<Y[i])){
++cur;
}
if(cur){
soma[cur-1]++;
}
}
int s=0;
for(int i=T-1;i!=-1;--i){
s+=soma[i];
pesos[vec[i].second]+=s;
}
}
for(auto&x:pesos)if(!x)return -1;
int count=0,retirou=0;
bool pegou[T]={};
for(;;){
++count;
std::vector<int> novA;
for(int i=0;i!=X.size();++i){
int pos=-1,valor = 1e9;
for(int j=0;j!=T;++j){
if(pegou[j])continue;
if(W[j]<X[i]){
if(pesos[j]<valor){
valor=pesos[j];
pos=j;
}
}
}
if(pos!=-1){
pegou[pos]=true;
++retirou;
novA.push_back(X[i]);
}
}
X=novA;
std::vector<int> novB;
for(int i=0;i!=Y.size();++i){
int pos=-1,valor=1e9;
for(int j=0;j!=T;++j){
if(pegou[j])continue;
if(S[j]<Y[i]){
if(pesos[j]<valor){
valor=pesos[j];
pos=j;
}
}
}
if(pos!=-1){
pegou[pos]=true;
novB.push_back(Y[i]);
++retirou;
}
}
Y=novB;
if(retirou==T){
break;
}
}
return count;
}
