#include "robots.h"
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const long long maxn = 1e6 + 10;
long long a, b, t;
long long x[maxn], y[maxn];
long long w[maxn], s[maxn];
struct robot
{
long long w, s, i;
robot(){};
robot(long long _w, long long _s, long long _i)
{
w = _w;
s = _s;
i = _i;
}
};
bool cmp(robot a, robot b)
{
return (a.w < b.w);
}
vector < robot > g;
long long mark[maxn];
bool check(long long mid)
{
for (long long i = 0; i < t; ++ i)
mark[i] = 0;
long long j = 0;
priority_queue < pair < long long, long long > > q;
for (long long i = 0; i < a; ++ i)
{
while(j < g.size() && g[j].w < x[i])
{
long long rs = g[j].s;
long long ri = g[j].i;
q.push({rs, ri});
j ++;
}
long long turn = mid;
while(turn -- && q.size())
{
long long ww = q.top().second;
// cout << "del " << q.top().first << " " << w[q.top().second] << endl;
q.pop();
mark[ww] = 1;
}
}
vector < pair < long long, long long > > u;
for (long long i = 0; i < t; ++ i)
{
if(mark[i])
{
//cout << "we marked something " << i << endl;
continue;
}
// cout << "left for small " << s[i] << " " << i << endl;
u.pb({s[i], i});
}
sort(u.begin(), u.end());
j = 0;
for (long long i = 0; i < b; ++ i)
{
long long turn = mid;
while(j < u.size() && u[j].first < y[i] && turn)
{
long long ri = u[j].second;
mark[ri] = 1;
j ++;
turn --;
}
}
for (long long i = 0; i < t; ++ i)
if(!mark[i])
{
// cout << i;
return false;
}
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 (long long i = 0; i < a; ++ i)
x[i] = X[i];
for (long long i = 0; i < b; ++ i)
y[i] = Y[i];
for (long long i = 0; i < t; ++ i)
{
w[i] = W[i];
s[i] = S[i];
g.pb(robot(w[i], s[i], i));
}
sort(x, x+a);
sort(y, y+b);
sort(g.begin(), g.end(), cmp);
long long l = 0, r = 1e6+1, mid, ans = 1e6+1;
while(l <= r)
{
mid = (l + r)/2;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(ans == 1e6+1)return -1;
else return ans;
}
