#include<bits/stdc++.h>
#include "robots.h"
#define fi first
#define se second
using namespace std;
const int TT=1e6;
struct Toy
{
int w,s,id;
};
Toy t1[TT+10],t2[TT+10];
bool vis[TT+10];
priority_queue<pair<int,int>> pq;
bool comp1(Toy a,Toy b)
{
return a.w<b.w;
}
bool comp2(Toy a,Toy b)
{
return a.s<b.s;
}
bool ok(int A,int B,int T,int X[],int Y[],int c)
{
for(int i=0;i<T;i++)
vis[i]=false;
while(!pq.empty())
pq.pop();
for(int i=0,j=0;i<A;i++)
{
while(j<T && t1[j].w<X[i])
{
pq.push({t1[j].s,t1[j].id});
j++;
}
for(int it=1;it<=c && !pq.empty();it++)
{
vis[pq.top().se]=true;
pq.pop();
}
}
for(int i=B-1,j=T-1;i>=0;i--)
{
for(int it=1;it<=c;)
{
if(j<0)
return true;
if(vis[t2[j].id])
j--;
else if(t2[j].s>=Y[i])
return false;
else
{
vis[t2[j].id]=true;
it++;
j--;
}
}
}
for(int i=0;i<T;i++)
{
if(!vis[i])
return false;
}
return true;
}
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++)
t1[i]=t2[i]={W[i],S[i],i};
sort(t1,t1+T,comp1);
sort(t2,t2+T,comp2);
int bg=1,en=T;
while(bg<en)
{
int mid=(bg+en)/2;
if(ok(A,B,T,X,Y,mid))
en=mid;
else
bg=mid+1;
}
if(ok(A,B,T,X,Y,bg))
return bg;
return -1;
}
