#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxt = 1e6 + 10;
const int maxn = 1e5 + 10;
struct toy
{
int w, s, idx;
toy(int _w = 0, int _s = 0, int _idx = 0)
{
w = _w;
s = _s;
}
} toys[maxt];
bool cmp_w(toy t1, toy t2)
{
return t1.w < t2.w;
}
bool cmp_s(toy t1, toy t2)
{
return t1.s < t2.s;
}
int x[maxn], y[maxn], used[maxt];
int a, b, t;
int cnt[maxn];
bool check(int p)
{
for (int i = 0; i < t; i ++)
used[i] = 0;
for (int i = 0; i < a; i ++)
{
//cout << i << endl;
int lf = 0, rf = t - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (toys[mf].w < x[i])
lf = mf + 1;
else
rf = mf - 1;
}
//cout << "Survived" << endl;
vector < toy > vec;
for (int j = 0; j < lf; j ++)
if (!used[j])
vec.push_back(toys[j]);
sort(vec.begin(), vec.end(), cmp_s);
int step = 0;
while(!vec.empty() && step < p)
{
used[vec.back().idx] = 1;
vec.pop_back();
step ++;
}
}
vector < toy > vec;
for (int i = 0; i < t; i ++)
if (!used[i])
vec.push_back(toys[i]);
sort(vec.begin(), vec.end(), cmp_s);
for (int i = 0; i < b; i ++)
cnt[i] = 0;
int pivot = 0;
for (toy cur : vec)
{
while(pivot < b && (cur.s >= y[pivot] || cnt[pivot] == p))
pivot ++;
if (pivot == b)
return false;
cnt[pivot] ++;
}
return true;
}
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 ++)
{
toys[i] = toy(W[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);
sort(toys, toys + T, cmp_w);
for (int i = 0; i < T; i ++)
toys[i].idx = i;
int lf = 0, rf = T;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (check(mf))
rf = mf - 1;
else
lf = mf + 1;
}
if (lf > T)
return - 1;
return lf;
}
