#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_T = 1000000;
const int MAX_R = 50000;
const int INF = 1000000001;
int A, B, T, X[MAX_R], Y[MAX_R];
pair<int, int> toy[MAX_T];
int norm(int coord, int sz, int *v) {
int st = -1, dr = sz;
while(dr - st > 1) {
int mid = (st + dr) / 2;
if(v[mid] <= coord)
st = mid;
else
dr = mid;
}
//X[dr] > coord; coord -> X[dr]
// dr == A => coord >= X[A - 1] => coord = INF;
if(dr < sz)
return v[dr];
return INF;
}
bool check(int cap) {
int lastup = 0;
priority_queue<int> q;
for(int i = 0; i < A; ++i) {
int x = cap;
//printf("Weak bot %d\n", X[i]);
while(lastup < T && toy[lastup].first == X[i]) {
//printf("insert; %d %d\n", toy[lastup].first, toy[lastup].second);
q.push(toy[lastup++].second);
}
while(!q.empty() && x > 0) {
//printf("assign %d\n", q.top());
q.pop();
x--;
}
}
while(lastup < T) {
//printf("insert: %d %d\n", toy[lastup].first, toy[lastup].second);
q.push(toy[lastup++].second);
}
for(int i = B - 1; i >= 0; --i) {
int x = cap;
//printf("Small bot: %d\n", Y[i]);
if(!q.empty() && q.top() > Y[i])
return false;
while(!q.empty() && x > 0) {
q.pop();
x--;
}
}
return q.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 < A; ++i)
X[i] = _X[i];
for(int i = 0; i < B; ++i)
Y[i] = _Y[i];
for(int i = 0; i < T; ++i)
toy[i] = make_pair(_W[i], _S[i]);
sort(X, X + A);
sort(Y, Y + B);
for(int i = 0; i < T; ++i) {
toy[i].first = norm(toy[i].first, A, X);
toy[i].second = norm(toy[i].second, B, Y);
if(toy[i].first == toy[i].second && toy[i].first == INF)
return -1;
}
sort(toy, toy + T);
int st, dr;
st = 0, dr = _T;
//printf("%d\n", check(4));
while(dr - st > 1) {
int mid = (st + dr) / 2;
if(check(mid))
dr = mid;
else
st = mid;
}
return dr;
}
