#include <bits/stdc++.h>
#include "robots.h"
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int offset=1<<20;
int *val[2];
int tree[2][offset<<1];
vector<pii> st[2][1000010];
void Up(int t,int h) {
while(h>0) {
if(tree[t][h*2+1]==-1||(tree[t][h*2]!=-1&&val[t][tree[t][h*2]]>val[t][tree[t][h*2+1]]))
tree[t][h]=tree[t][h*2];
else tree[t][h]=tree[t][h*2+1];
h/=2;
}
}
void Add(int t,int p,int x,int i) {
st[t][p].push_back({x,i});
}
void Remove(int t,int p) {
st[t][p].pop_back();
if(st[t][p].empty()) tree[t][p+offset]=-1;
else tree[t][p+offset]=st[t][p].back().se;
Up(t,(p+offset)/2);
}
int query(int t,int l,int r) {
if(l>r) return -1;
int ret=-1;
l+=offset,r+=offset;
while(1) {
if(ret==-1||(tree[t][l]!=-1&&val[t][ret]<val[t][tree[t][l]])) ret=tree[t][l];
if(ret==-1||(tree[t][r]!=-1&&val[t][ret]<val[t][tree[t][r]])) ret=tree[t][r];
if(l==r) break;
l=(l+1)>>1;
r=(r-1)>>1;
}
return ret;
}
int putaway (int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,j;
memset(tree,-1,sizeof(tree));
vector<int> v,w;
sort(X,X+A); sort(Y,Y+B);
val[0]=S,val[1]=W;
for(i=0;i<T;i++) {
v.push_back(W[i]);
w.push_back(S[i]);
}
sort(all(v));
v.erase(unique(all(v)),v.end());
sort(all(w));
w.erase(unique(all(w)),w.end());
for(i=0;i<A;i++) {
X[i]=lower_bound(all(v),X[i])-v.begin();
}
for(i=0;i<B;i++) {
Y[i]=lower_bound(all(w),Y[i])-w.begin();
}
for(i=0;i<T;i++){
W[i]=lower_bound(all(v),W[i])-v.begin()+1;
S[i]=lower_bound(all(w),S[i])-w.begin()+1;
Add(0,W[i],S[i],i);
Add(1,S[i],W[i],i);
}
for(i=1;i<=sz(v);i++) {
sort(all(st[0][i]));
tree[0][i+offset]=st[0][i].empty()?-1:st[0][i].back().se;
Up(0,(i+offset)/2);
}
for(i=1;i<=sz(w);i++) {
sort(all(st[1][i]));
tree[1][i+offset]=st[1][i].empty()?-1:st[1][i].back().se;
Up(1,(i+offset)/2);
}
int ans=0,q; bool flag;
while(1) {
flag=false;
for(i=0;T&&i<A;i++) {
q=query(0,0,X[i]);
if(q==-1) continue;
Remove(0,W[q]);
Remove(1,S[q]);
T--; flag=true;
}
for(i=0;T&&i<B;i++) {
q=query(1,0,Y[i]);
if(q==-1) continue;
Remove(0,W[q]);
Remove(1,S[q]);
T--; flag=true;
}
ans++;
if(!T) break;
if(!flag) {
return -1;
}
}
return ans;
}
