#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w,h;
vector<pair<int,int>> coords;
struct Node{
int s,e;
ll sum = 0;
ll suffmin = 0;
Node *l, *r;
Node(int _s, int _e){
s=_s; e=_e;
if (s==e){
return;
}
l = new Node(s,(s+e)/2);
r = new Node((s+e)/2+1,e);
}
void clear(ll mid){
if (s==e){
if (e!=h-1){
sum = mid;
} else {
sum = 0;
}
suffmin = min(0LL, mid);
return;
}
l->clear(mid);
r->clear(mid);
sum = l->sum + r->sum;
suffmin = min(l->suffmin+r->sum,r->suffmin);
}
void decrement(int ind){
int m = (s+e)/2;
if (s==e){
sum--;
suffmin = min(suffmin,sum);
return;
}
if (ind<=m){
l->decrement(ind);
} else {
r->decrement(ind);
}
sum = l->sum + r->sum;
suffmin = min(l->suffmin+r->sum,r->suffmin);
}
};
Node *root;
bool success(ll mid){
root->clear(mid);
for (auto c : coords){
ll x = c.first;
ll y = c.second;
root->decrement(y);
ll numobjs = root->suffmin;
ll val = mid*(w-1-x);
if (val+numobjs<0){return false;}
}
return true;
}
int putaway(int lx, int ly, int n, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
sort(xpos,xpos+lx);
sort(ypos,ypos+ly);
for (ll i = 0; i<n; i++){
xtoys[i]=upper_bound(xpos,xpos+lx,xtoys[i])-xpos;
ytoys[i]=upper_bound(ypos,ypos+ly,ytoys[i])-ypos;
}
w=lx+1;
h=ly+1;
for (ll i = 0; i<n; i++){
coords.push_back({xtoys[i],ytoys[i]});
if (xtoys[i]==w-1&&ytoys[i]==h-1){
return -1;
}
}
sort(coords.rbegin(), coords.rend());
ll l = 0, r = n;
root = new Node(0,h-1);
while (l<=r){
ll mid = (l+r)/2;;
if (success(mid)){
r=mid-1;
} else {
l=mid+1;
}
}
return l;
}
