#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X , X + A);
sort(Y , Y + B);
auto igA = [&](int x){
int p = -1;
for(int bit = 17;bit >= 0;bit --){
p += 1 << bit;
if(p >= A){
p -= 1 << bit;
}else if(X[p] > x){
p -= 1 << bit;
}
}
++p;
return A - p;
};
auto igB = [&](int x){
int p = -1;
for(int bit = 17;bit >= 0;bit --){
p += 1 << bit;
if(p >= B){
p -= 1 << bit;
}else if(Y[p] > x){
p -= 1 << bit;
}
}
++p;
return B - p;
};
vector<int> cA(T) , cB(T);
for(int i = 0;i < T;i ++){
cA[i] = igA(W[i]);
cB[i] = igB(S[i]);
if(cA[i] + cB[i] == 0){
return -1;
}
}
vector<int> oy(T);
iota(oy.begin() , oy.end() , 0);
sort(oy.begin() , oy.end() , [&](int i , int j){
return pair<int , int>{cB[i] , -cA[i]} < pair<int , int>{cB[j] , -cA[j]};
});
reverse(oy.begin() , oy.end());
auto solveB = [&](vector<int> v){
vector<int> c(B + 1);
for(int x : v){
c[x]++;
}
int ans = 0;
for(int i = 1;i <= B;i ++){
c[i] += c[i - 1];
ans = max(ans , (c[i] + i - 1) / i);
}
return ans;
};
vector<int> t(4 * A) , lz(4 * A);
auto push = [&](int u){
t[u * 2] += lz[u];
t[u * 2 + 1] += lz[u];
lz[u * 2] += lz[u];
lz[u * 2 + 1] += lz[u];
lz[u] = 0;
};
function<void(int , int , int , int , int , int)> update = [&](int u , int l , int r , int L , int R , int x){
if(l > r || r < L || l > R){
return;
}
if(L <= l && r <= R){
t[u] += x;
lz[u] += x;
return;
}
int m = (l + r) / 2;
push(u);
update(u * 2 , l , m , L , R , x);
update(u * 2 + 1 , m + 1 , r , L , R , x);
t[u] = min(t[u * 2] , t[u * 2 + 1]);
};
function<int(int , int , int , int , int)> query = [&](int u , int l , int r , int L , int R){
if(l > r || r < L || l > R){
return (int)1E9;
}
if(L <= l && r <= R){
return t[u];
}
int m = (l + r) / 2;
push(u);
return min(query(u * 2 , l , m , L , R) , query(u * 2 + 1 , m + 1 , r , L , R));
};
function<void(int , int , int , int)> build = [&](int u , int l , int r , int v){
lz[u] = 0;
if(l == r){
long long A = 1LL * r * v;
A = min(A , (long long)1E6);
t[u] = A;
return;
}
int m = (l + r) / 2;
build(u * 2 , l , m , v);
build(u * 2 + 1 , m + 1 , r , v);
t[u] = min(t[u * 2] , t[u * 2 + 1]);
};
auto pos = [&](int v){
vector<int> pref(A + 1) , left;
build(1 , 1 , A , v);
auto can_insert = [&](int x){
return (query(1 , 1 , A , x , A) > 0);
};
auto insert = [&](int x){
update(1 , 1 , A , x , A , -1);
};
for(int i = 0;i < T;i ++){
if(!cA[i]){
left.emplace_back(cB[i]);
}else if(!cB[i]){
if(!can_insert(cA[i])){
return false;
}
insert(cA[i]);
}
}
for(int i = T - 1;i >= 0;i --){
int j = oy[i];
if(!cA[j] || !cB[j]){
continue;
}
if(can_insert(cA[j])){
insert(cA[j]);
}else{
left.emplace_back(cB[j]);
}
}
return solveB(left) <= v;
};
int ans = 0;
for(int bit = 20;bit >= 0;bit --){
ans += 1 << bit;
if(pos(ans) == true){
ans -= 1 << bit;
}
}
++ans;
return ans;
}
