#include <algorithm>
#include <vector>
#include <map>
#include "robots.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e6 + 5, LOG = 18, MOD = 1e9 + 7;
struct Point {
int x,y;
bool operator< (const Point &o) const {
return make_pair(x,y) < make_pair(o.x,o.y);
}
};
bool cmp (const Point &a, const Point &b) {return make_pair(a.y,a.x) < make_pair(b.y,b.x);}
struct Segtree {
pii tree[2097155];
void build (int ind, int l, int r, vector<int> &v) {
if (l == r) return (void) (tree[ind] = {v[l-1],l-1});
int mid = (l + r) / 2;
build(lc,l,mid,v); build(rc,mid+1,r,v);
tree[ind] = max(tree[lc],tree[rc]);
}
int findfirst (int ind, int l, int r) {
if (l == r) return tree[ind].first > 0 ? l-1 : -1;
int mid = (l + r) / 2;
if (tree[lc].first > 0) return findfirst(lc,l,mid);
return findfirst(rc,mid+1,r);
}
void update (int ind, int l, int r, int i, int v) {
if (l == r) return (void) (tree[ind] = {v,l-1});
int mid = (l + r) / 2;
if (i <= mid) update(lc,l,mid,i,v);
else update(rc,mid+1,r,i,v);
tree[ind] = max(tree[lc],tree[rc]);
}
pii query (int ind, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return {-1,-1};
if (l <= tl && tr <= r) return tree[ind];
int mid = (tl + tr) / 2;
return max(query(lc,tl,mid,l,r),query(rc,mid+1,tr,l,r));
}
} xSeg, ySeg;
int putaway (int a, int b, int t, int *x, int *y, int *w, int *s) { //2 segtree + bsearch
sort(x,x+a); sort(y,y+b);
vector<Point> xSrt(t), ySrt(t);
for (int i = 0; i < t; i++) xSrt[i] = ySrt[i] = {w[i],s[i]};
sort(xSrt.begin(),xSrt.end());
sort(ySrt.begin(),ySrt.end(),cmp);
vector<int> temp(t);
for (int i = 0; i < t; i++) temp[i] = xSrt[i].y;
xSeg.build(1,1,t,temp);
for (int i = 0; i < t; i++) temp[i] = ySrt[i].x;
ySeg.build(1,1,t,temp);
map<Point,int> taken;
auto del = [&] (Point &p) {
//printf ("p {%d,%d}\n",p.x,p.y);
int posX = lower_bound(xSrt.begin(),xSrt.end(),p) - xSrt.begin() + taken[p];
int posY = lower_bound(ySrt.begin(),ySrt.end(),p,cmp) - ySrt.begin() + taken[p];
taken[p]++;
//printf ("posX %d posY %d\n",posX,posY);
xSeg.update(1,1,t,posX+1,-1e9); ySeg.update(1,1,t,posY+1,-1e9);
};
int ret = 0, done = 0;
while (done < t) {
++ret; bool add = 0;
int lstLine = -1;
while (1) {
int go = xSeg.findfirst(1,1,t);
//printf ("go %d\n",go);
if (go == -1) break;
int nxtLine = max(lstLine + 1,(int)(upper_bound(x,x+a,xSrt[go].x)-x));
//printf ("nxtLine %d\n",nxtLine);
if (nxtLine >= a) break;
int ed = lower_bound(xSrt.begin(),xSrt.end(),Point{x[nxtLine],0})-xSrt.begin();
//printf ("ed %d\n",ed);
int take = xSeg.query(1,1,t,1,ed).second;
//printf ("take %d\n",take);
del(xSrt[take]); add = 1; ++done; lstLine = nxtLine;
}
lstLine = -1;
while (1) {
int go = ySeg.findfirst(1,1,t);
//printf ("y go %d\n",go);
if (go == -1) break;
int nxtLine = max(lstLine + 1,(int)(upper_bound(y,y+b,ySrt[go].y)-y));
//printf ("y nxtLine %d\n",nxtLine);
if (nxtLine >= b) break;
int ed = lower_bound(ySrt.begin(),ySrt.end(),Point{0,y[nxtLine]},cmp)-ySrt.begin();
//printf ("y ed %d\n",ed);
int take = ySeg.query(1,1,t,1,ed).second;
//printf ("y take %d\n",take);
del(ySrt[take]); add = 1; ++done; lstLine = nxtLine;
}
if (!add) return -1;
}
return ret;
}
