#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w,h;
vector<pair<ll,ll>> coords;
struct Fenwick{
vector<ll> fenwick;
int n;
Fenwick(int _n){
n=_n;
fenwick.resize(n+1);
}
void update(int ind, int val){
ind++;
while (ind<=n){
fenwick[ind]+=val;
ind+=ind&(-ind);
}
}
ll query(int ind){
ind++;
ll ans=0;
while (ind>0){
ans+=fenwick[ind];
ind-=ind&(-ind);
}
return ans;
}
};
bool success(ll mid){
Fenwick f(h+1);
for (auto c : coords){
int x = c.first;
int y = c.second;
f.update(h-y,1);
ll numobjs = f.query(h-y);
ll val = mid*(w-1-x+h-1-y);
//cout<<x<<' '<<y<<' '<<numobjs<<' '<<val<<endl;
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;
while (l<=r){
ll mid = (l+r)/2;;
if (success(mid)){
r=mid-1;
} else {
l=mid+1;
}
}
return l;
}
