#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int a,b,t;
int x[50005], y[50005];
int w[1000005], s[1000005];
vector<int> v(1000005);
bool cmpw(int a, int b){
return w[a] < w[b];
}
bool cando(int pp){
//printf("\t\t\t\tTesting %d\n",pp);
int curT = 0, curA = 0;
priority_queue<int> pq;
while (curT < t && curA < a){
if (x[curA] <= w[v[curT]]){
int num = 0;
while (num++ < pp && pq.size()){
//printf("popping %d\n",pq.top());
pq.pop();
}
curA++;
}
else{
//printf("pushing %d\n",s[v[curT]]);
pq.push(s[v[curT]]);
curT++;
}
}
//printf("%d %d %d\n",pq.size(),curA,a);
for (long long i = 0; i < (long long)(a-curA)*pp && pq.size(); i++){
//printf("popping %d\n",pq.top());
pq.pop();
}
//printf("%d %d\n",curT,t);
while (curT < t){
//printf("pushing %d\n",s[v[curT]]);
pq.push(s[v[curT++]]);
}
int curB = b-1;
//printf("%d ",pq.size());
while (curB >= 0 && pq.size()){
//printf("%d %d\n",y[curB],pq.top());
if (y[curB] <= pq.top()) return false;
else{
int num = 0;
while (num++ < pp && pq.size()){
//printf("popping %d\n",pq.top());
//printf("robot %d takes size %d\n",curB,pq.top());
pq.pop();
}
curB--;
}
}
return pq.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A, b = B, t = T;
for (int i = 0; i < t; i++){
w[i] = W[i];
s[i] = S[i];
}
for (int i = 0; i < a; i++){
x[i] = X[i];
}
for (int i = 0; i < b; i++){
y[i] = Y[i];
}
sort(x,x+a);
sort(y,y+b);
int lo = 0, hi = t+1;
v.resize(t);
for (int i = 0; i < t; i++) v[i] = i;
sort(v.begin(),v.end(),cmpw);
while (lo + 1 < hi){
//printf("%d %d\n",lo,hi);
int mid = (lo+hi)/2;
if (cando(mid)){
hi = mid;
}
else lo = mid;
}
if (lo + 1 == hi){
//printf("%d %d\n",lo,hi);
if (cando(lo)) hi = lo;
else lo = hi;
}
if (lo == t+1) return -1;
return lo;
}
