#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define st first
#define nd second
#define orta ((bas+son)/2)
#define MAX1 1000005
#define MAX2 50005
int A,B,T;
int X[MAX2],Y[MAX2];
ii toy[MAX1];
bool S[2][MAX2*4];
int fr[2][MAX2];
int DAYS;
void build(int node,int bas,int son,int w) {
if(bas>son) return ;
if(bas==son) {
fr[w][bas]=0;
S[w][node]=true;
return ;
}
build(node*2,bas,orta,w);
build(node*2+1,orta+1,son,w);
S[w][node]=S[w][node*2]|S[w][node*2+1];
}
priority_queue<int> H;
void zero() {
while(!H.empty()) H.pop();
build(1,0,A-1,0);
build(1,0,B-1,1);
}
void up(int node,int bas,int son,int x,int w) {
if(bas>x || son<x) return ;
if(bas==x && son==x) {
S[w][node]=false;
return ;
}
up(node*2,bas,orta,x,w);
up(node*2+1,orta+1,son,x,w);
S[w][node]=S[w][node*2]|S[w][node*2+1];
}
int get(int node,int bas,int son,int x,int y,int w) {
if(bas>=x && son<=y) {
if(!S[w][node]) return bas;
if(bas==son) return bas;
if(S[w][node*2]) return get(node*2,bas,orta,x,y,w);
return get(node*2+1,orta+1,son,x,y,w);
}
if(orta>=x) {
if(orta+1<=y) {
int L=get(node*2,bas,orta,x,y,w);
if(fr[w][L]<DAYS) return L;
return get(node*2+1,orta+1,son,x,y,w);
}
return get(node*2,bas,orta,x,y,w);
}
return get(node*2+1,orta+1,son,x,y,w);
}
bool check() {
zero();
int last=A;
for(int i=0;i<T;i++) {
while(last-1>=0 && X[last-1]>=toy[i].st) last--;
int RASA=(last<A?get(1,0,A-1,last,A-1,0):-1);
H.push(-toy[i].nd);
if(last==A || fr[0][RASA]==DAYS) {
int valB=-H.top();
H.pop();
int pos=lower_bound(Y,Y+B,valB)-Y;
int RASB=(pos<B?get(1,0,B-1,pos,B-1,1):-1);
if(pos==B || fr[1][RASB]==DAYS) {
return false;
}
else {
fr[1][RASB]++;
if(fr[1][RASB]==DAYS) {
up(1,0,B-1,RASB,1);
}
}
}
else {
fr[0][RASA]++;
if(fr[0][RASA]==DAYS) {
up(1,0,A-1,RASA,0);
}
}
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
::A=A;
::B=B;
::T=T;
for(int i=0;i<A;i++) {
X[i]--;
::X[i]=X[i];
}
for(int i=0;i<B;i++) {
Y[i]--;
::Y[i]=Y[i];
}
for(int i=0;i<T;i++) {
toy[i]={W[i],S[i]};
}
sort(::X,::X+A);
sort(::Y,::Y+B);
sort(toy,toy+T,greater<ii>());
int bas=1,son=T;
while(bas<=son) {
DAYS=orta;
if(check()) son=orta-1;
else bas=orta+1;
}
if(bas==T+1) {
return -1;
}
return bas;
}
