#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w,h;
//map<ll,int> grid;
int indices[1000000];
ll dp[2][50001];
//ll m = 1e9;
int vals[1000000];
int xcs[1000000];
int ycs[1000000];
int vtot=0;
int *xc, *yc;
int n;
int ns;
int nc=0;
ll gcd2(ll a, ll b){
return a+b;
}
struct NodeY{
int s,e;
ll v;
NodeY *l = NULL;
NodeY *r = NULL;
NodeY(int _s, int _e){
nc++;
s=_s;e=_e;
v=0;
}
void makeL(){
if (l!=NULL){
return;
}
l = new NodeY(s,(s+e)/2);
}
void makeR(){
if (r!=NULL){
return;
}
r = new NodeY((s+e)/2+1,e);
}
ll getL(){
if (l==NULL){
return 0;
}
return l->v;
}
ll getR(){
if (r==NULL){
return 0;
}
return r->v;
}
void update(int ind, ll val){
//cout<<"y "<<s<<' '<<e<<'\n';
//cout<<"u "<<ind<<' '<<val<<'\n';
if (s==e){
v=val;
return;
}
if (ind<=(s+e)/2){
makeL();
l->update(ind,val);
} else {
makeR();
r->update(ind,val);
}
v=gcd2(getL(),getR());
}
ll queryL(int ya, int yb){
if (l==NULL){
return 0;
}
return l->query(ya,yb);
}
ll queryR(int ya, int yb){
if (r==NULL){
return 0;
}
return r->query(ya,yb);
}
ll query(int ya, int yb){
if (s==ya&&e==yb){
return v;
}
int m = (s+e)/2;
if (yb<=m){
return queryL(ya,yb);
} else if (m<ya){
return queryR(ya,yb);
} else {
return gcd2(queryL(ya,m),queryR(m+1,yb));
}
}
void combine(NodeY *lc, NodeY *rc, int ind){
//cout<<s<<' '<<e<<' '<<"com\n";
int m = (s+e)/2;
if (s==e){
v=gcd2((lc==NULL)?0:lc->v,(rc==NULL)?0:rc->v);
return;
}
if (lc==NULL&&rc==NULL){
v=0;
return;
}
if (ind<=m){
makeL();
l->combine((lc==NULL)?(NodeY*)NULL:lc->l,(rc==NULL)?(NodeY*)NULL:rc->l,ind);
} else {
makeR();
r->combine((lc==NULL)?(NodeY*)NULL:lc->r,(rc==NULL)?(NodeY*)NULL:rc->r,ind);
}
v=gcd2((l==NULL)?0:l->v,(r==NULL)?0:r->v);
}
};
struct NodeX{
int s,e;
NodeY *v;
NodeX *l = NULL;
NodeX *r = NULL;
NodeX(int _s, int _e){
nc++;
s=_s;e=_e;
v=new NodeY(0,ns-1);
}
void makeL(){
if (l!=NULL){
return;
}
l = new NodeX(s,(s+e)/2);
}
void makeR(){
if (r!=NULL){
return;
}
r = new NodeX((s+e)/2+1,e);
}
void update(int indx, int indy, ll val){
//cout<<"x "<<s<<' '<<e<<'\n';
//cout<<"u "<<indx<<' '<<indy<<' '<<val<<'\n';
if (s==e){
v->update(indy,val);
return;
}
if (indx<=(s+e)/2){
makeL();
l->update(indx,indy,val);
} else {
makeR();
r->update(indx,indy,val);
}
//cout<<"combine\n";
v->combine((l==NULL)?(NodeY*)NULL:l->v,(r==NULL)?(NodeY*)NULL:r->v,indy); //???
}
ll queryL(int xa, int xb, int ya, int yb){
if (l==NULL){
return 0;
}
return l->query(xa,xb,ya,yb);
}
ll queryR(int xa, int xb, int ya, int yb){
if (r==NULL){
return 0;
}
return r->query(xa,xb,ya,yb);
}
ll query(int xa, int xb, int ya, int yb){
int m = (s+e)/2;
assert(xa<=xb&&ya<=yb);
if (s==xa&&e==xb){
return v->query(ya,yb);
}
if (xb<=m){
return queryL(xa,xb,ya,yb);
} else if (m<xa){
return queryR(xa,xb,ya,yb);
} else {
return gcd2(queryL(xa,m,ya,yb),queryR(m+1,xb,ya,yb));
}
}
};
NodeX *root;
bool success(ll mid){
ns=h;
root = new NodeX(0,w-1);
/*for (int y = 0; y<2; y++){
for (int x = 0; x<=w; x++){
dp[y][x]=0;
}
}
for (ll i = w-1; i>=0; i--){
dp[0][i]=mid*(w-1-i);
}*/
/*bool c = 1;
int cnt = 0;
for (ll y = h-1; y>=0; y--){
dp[c][w]=mid*(h-1-y);
for (ll x = w-1; x>=0; x--){
dp[c][x]=dp[c][x+1]+dp[!c][x]-dp[!c][x+1];//-grid[x*m+y];
while (cnt<vtot&&xcs[cnt]==x&&ycs[cnt]==y){
dp[c][x]-=vals[cnt];
cnt++;
}
if (dp[c][x]<0){
return false;
}
}
c=!c;
}*/
for (int cnt = 0; cnt<vtot; cnt++){
ll val = root->query(xcs[cnt],w-1,ycs[cnt],h-1);
ll tot = mid*(h-1-ycs[cnt]+w-1-xcs[cnt]);
if (tot-val-vals[cnt]<0){
return false;
}
root->update(xcs[cnt],ycs[cnt],vals[cnt]);
}
return true;
}
bool comp(int a, int b){
if (yc[a]==yc[b]){
return xc[a]>xc[b];
} else {
return yc[a]>yc[b];
}
}
int putaway(int lx, int ly, int N, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
n=N;
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;
xc=xtoys;yc=ytoys;
//grid.resize(w,vector<ll>(h,0));
/*for (ll i = 0; i<n; i++){
grid[(xtoys[i])*m+ytoys[i]]++;
}
if (grid[(w-1)*m+h-1]>0){
return -1;
}*/
for (int i = 0; i<n; i++){
indices[i]=i;
}
sort(indices,indices+n,comp);
int curx = xtoys[indices[0]];
int cury = ytoys[indices[0]];
int cnt = 0;
for (int i = 0; i<n; i++){
if (xtoys[indices[i]]==curx&&xtoys[indices[i]]==cury){
cnt++;
} else {
xcs[vtot]=curx;
ycs[vtot]=cury;
vals[vtot]=cnt;
curx=xtoys[indices[i]];
cury=ytoys[indices[i]];
vtot++;
cnt=1;
}
}
if (cnt>0){
xcs[vtot]=curx;
ycs[vtot]=cury;
vals[vtot]=cnt;
vtot++;
}
/*for (int i = 0; i<n; i++){
cout<<xtoys[indices[i]]<<' '<<ytoys[indices[i]]<<'\n';
}*/
if (xtoys[indices[0]]==w-1&&ytoys[indices[0]]==h-1){
return -1;
}
/*for (int i = 0; i<xcs.size(); i++){
cout<<xcs[i]<<' '<<ytoys[i]<<' '<<vals[i]<<'\n';
}*/
ll l = 0, r = n;
while (l<=r){
ll mid = (l+r)/2;;
if (success(mid)){
r=mid-1;
} else {
l=mid+1;
}
}
}
