#include "robots.h"
#include <algorithm>
#include <queue>
using namespace std;
pair <int,int> Toy[1000000];
int A, B, T, X[50000], Y[50000], Ans;
int OK(int Limit)
{
priority_queue <int> Q;
int i, j, k;
j=0;
for(i=0 ; i<A ; i++)
{
while(Toy[j].first<X[i] && j<T)
{
Q.push(Toy[j].second);
j++;
}
for(k=1 ; k<=Limit ; k++)
{
if(Q.empty())
break;
Q.pop();
}
}
for(i=j ; i<T ; i++)
Q.push(Toy[i].second);
if(Q.empty())
return 1;
for(i=B-1 ; i>=0 ; i--)
for(j=1 ; j<=Limit ; j++)
{
if(Q.empty())
return 1;
k=Q.top();
Q.pop();
if(k>=Y[i])
return 0;
}
if(Q.empty())
return 1;
return 0;
}
int putaway(int A_, int B_, int T_, int X_[], int Y_[], int W[], int S[])
{
int i, Left, Mid, Right;
A=A_;
B=B_;
T=T_;
for(i=0 ; i<A ; i++)
X[i]=X_[i];
for(i=0 ; i<B ; i++)
Y[i]=Y_[i];
for(i=0 ; i<T ; i++)
Toy[i]=make_pair(W[i],S[i]);
sort(X,X+A);
sort(Y,Y+B);
sort(Toy,Toy+T);
Left=1;
Right=T;
Ans=-1;
while(Left<=Right)
{
Mid=(Left+Right)/2;
if(OK(Mid))
{
Right=Mid-1;
Ans=Mid;
}
else
Left=Mid+1;
}
return Ans;
}
