#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
struct node {
int id,x,y;
node(int _id = 0,int _x = 0,int _y = 0) {
id = _id; x = _x; y = _y;
}
};
int n,m,k;
int a[50005], b[50005];
int tree[200005], L[200005], R[200005];
bool ok[1000005];
node px[1000005], py[1000005];
bool cmpx(node x,node y) {
return x.x>y.x;
}
bool cmpy(node x,node y) {
return x.y>y.y;
}
void build(int* p,int pos,int l,int r,int val) {
if(l==r) {
tree[pos] = val;
L[pos] = R[pos] = p[l];
// printf("tree [%d, %d] = %d : {%d, %d}\n",l,r,tree[pos],L[pos],R[pos]);
return ;
}
int mid = (l+r)/2;
build(a,pos<<1,l,mid,val); build(a,pos<<1|1,mid+1,r,val);
tree[pos] = tree[pos<<1] + tree[pos<<1|1];
L[pos] = L[pos<<1]; R[pos] = R[pos<<1|1];
// printf("tree [%d, %d] = %d : {%d, %d}\n",l,r,tree[pos],L[pos],R[pos]);
}
int query(int pos,int l,int r,int val) {
// printf("query [%d, %d] : %d R = %d\n",l,r,val,R[pos]);
if(l>r || R[pos]<=val) return inf;
// printf("!go [%d, %d] : %d\n",l,r,val);
if(L[pos]>val && tree[pos]>0) return l;
int mid = (l+r)/2;
return min(query(pos<<1,l,mid,val), query(pos<<1|1,mid+1,r,val));
}
void update(int pos,int l,int r,int x) {
if(l>x || r<x) return ;
if(l==r) {
tree[pos]--;
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x); update(pos<<1|1,mid+1,r,x);
tree[pos] = tree[pos<<1] + tree[pos<<1|1];
}
bool check(int cnt) {
int i,x;
memset(ok,0,sizeof(ok));
build(a,1,0,n-1,cnt);
return 0;
for(i=0;i<k;i++) {
x = query(1,0,n-1,py[i].x);
// printf("1) %d %d => %d\n",py[i].x,py[i].y,x);
if(x==inf) continue;
update(1,0,n-1,x);
ok[py[i].id] = 1;
}
build(b,1,0,m-1,cnt);
for(i=0;i<k;i++) {
if(ok[px[i].id]) continue;
// printf("2) %d %d => %d\n",px[i].x,px[i].y,x);
x = query(1,0,m-1,px[i].y);
if(x==inf) continue;
update(1,0,m-1,x);
ok[px[i].id] = 1;
}
for(i=0;i<k;i++) if(!ok[i]) return 0;
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,l,r,mid,ans;
n = A; m = B; k = T;
for(i=0;i<n;i++) a[i] = X[i];
for(i=0;i<m;i++) b[i] = Y[i];
for(i=0;i<k;i++) px[i] = py[i] = node(i,W[i],S[i]);
sort(&px[0],&px[k],cmpx);
sort(&py[0],&py[k],cmpy);
sort(&a[0],&a[n]);
sort(&b[0],&b[m]);
l = 1; r = k; ans = -1;
while(l<=r) {
mid = (l+r)/2;
// printf("check %d\n",mid);
if(check(mid)) {
ans = mid;
r = mid-1;
}
else l = mid+1;
}
return ans;
}
