#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10 , M = 5e4 + 10;
int a , b , t , x[M] , y[M];
struct item{
int w , s;
} ar[N];
bool cmp(item aa , item bb)
{
return aa.s > bb.s;
}
struct SEG{
int mx[N << 2];
void Set(int id , int vl , int node = 1 , int nl = 0 , int nr = M)
{
if(nr - nl == 1)
{
mx[node] = vl;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(id < mid)
Set(id , vl , lc , nl , mid);
else
Set(id , vl , rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
void Rem(int id , int node = 1 , int nl = 0 , int nr = M)
{
if(nr - nl == 1)
{
mx[node]--;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(id < mid)
Rem(id , lc , nl , mid);
else
Rem(id , rc , mid , nr);
mx[node] = max(mx[lc] , mx[rc]);
}
int Get(int id , int node = 1 , int nl = 0 , int nr = M)
{
if(id >= nr || mx[node] == 0)
return -1;
if(nr - nl == 1)
{
return nl;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
int L = Get(id , lc , nl , mid);
if(L != -1)
return L;
return Get(id , rc , mid , nr);
}
} cx , cy;
bool Check(int mid)
{
for(int i = 0 ; i < a ; i++)
cx.Set(i , mid);
for(int i = 0 ; i < b ; i++)
cy.Set(i , mid);
bool flg = true;
for(int i = 0 ; i < t ; i++)
{
int A = upper_bound(x , x + a , ar[i].w) - x;
int B = upper_bound(y , y + a , ar[i].s) - y;
A = cx.Get(A);
B = cy.Get(B);
if(A != -1)
cx.Rem(A);
else if(B != -1)
cy.Rem(B);
else
{
flg = false;
break;
}
}
return flg;
}
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];
sort(x , x + a);
sort(y , y + b);
for(int i = 0 ; i < T ; i++)
{
ar[i] = {W[i] , S[i]};
}
sort(ar , ar + T , cmp);
int low = 0 , high = T + 1;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(Check(mid))
high = mid;
else
low = mid;
}
if(high == T + 1)
return -1;
return high;
}
