#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const int maxn=1e6+5;
const int maxa=5e4+5;
int w[maxn],s[maxn];
int x[maxa],y[maxa];
int sz[maxn],weight[maxn];
bool used[maxn];
bool cmpsz(int a,int b)
{
if(s[a]!=s[b])
return s[a]<s[b];
return w[a]<w[b];
}
bool cmpw(int a,int b)
{
if(w[a]!=w[b])
return w[a]<w[b];
return s[a]<s[b];
}
int bin_search_w(int src,int & T)
{
int l=0,r=T-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(w[weight[mid]]<src)
l=mid+1;
else
r=mid-1;
}
return l-1;
}
int bin_search_s(int src,int & T)
{
int l=0,r=T-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(s[sz[mid]]<src)
l=mid+1;
else
r=mid-1;
}
return l-1;
}
bool check(int curr,int & A,int & B,int & T)
{
//cout<<"curr "<<curr<<endl;
for(int i=0;i<T;i++)
used[i]=false;
multiset<pair<int,int>> st; // (size, index)
int idx = 0;
for(int i=0;i<A;i++)
{
// add all toys this robot can lift
while(idx < T && w[weight[idx]] < x[i])
{
int id = weight[idx];
if(!used[id])
st.insert({s[id], id});
idx++;
}
int cnt = 0;
while(!st.empty() && cnt < curr)
{
// take the toy with LARGEST size (hardest for small robots)
auto it = prev(st.end());
int id = it->second;
used[id] = true;
st.erase(it);
cnt++;
}
}
st.clear();
idx=0;
for(int i=0;i<B;i++)
{
while(idx < T && s[sz[idx]] < y[i])
{
int id = sz[idx];
if(!used[id])
st.insert({w[id], id});
idx++;
}
int cnt = 0;
while(!st.empty() && cnt < curr)
{
// take the toy with LARGEST weight
auto it = prev(st.end());
int id = it->second;
used[id] = true;
st.erase(it);
cnt++;
}
}
for(int i=0;i<T;i++)
{
if(!used[i])
return false;
}
return true;
}
int putaway(int A, int B, int T,int X[], int Y[], int W[], int S[])
{
for(int i=0;i<A;i++)
x[i]=X[i];
for(int i=0;i<B;i++)
y[i]=Y[i];
for(int i=0;i<T;i++)
{
sz[i]=i;
weight[i]=i;
w[i]=W[i]; s[i]=S[i];
}
sort(sz,sz+T,cmpsz);
sort(weight,weight+T,cmpw);
sort(x,x+A);
sort(y,y+B);
int l=1,r=T,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,A,B,T))
r=mid-1;
else
l=mid+1;
}
if(l>T)
return -1;
return l;
}
