#include <bits/stdc++.h>
#include "robots.h"
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define for1(i, n) for(int i = 1; i <= int(n); ++ i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
using namespace std;
struct ura {
int w, s, idx;
};
struct ura2 {
int pos, t;
const bool operator < (const ura2 & a) const {
return t < a.t;
}
};
const int maxn = 1e6;
const int maxr = 5e4;
int robot1[maxr];
int robot2[maxr];
ura peso[maxn];
ura tamanio[maxn];
bool usados[maxn];
int n, m, t;
priority_queue<ura2> pq;
bool ordena1 (ura a, ura b){
return a.w < b.w;
}
bool ordena2 (ura a, ura b) {
return a.s < b.s;
}
void limpiar(){
while(!pq.empty()){
pq.pop();
}
}
bool probar(int aux){
memset(usados, 0, sizeof(usados));
int cant = 0;
int idx = 0;
limpiar();
for0(i, n){
forn(j, idx, t - 1){
if(peso[j].w < robot1[i]){
pq.push({peso[j].idx, peso[j].s});
idx ++;
continue;
}
break;
}
cant += min((int) pq.size(), aux);
int aux2 = (int) pq.size();
for0(i, min(aux2, aux)){
ura2 act = pq.top();
usados[act.pos] = 1;
pq.pop();
}
}
limpiar();
idx = 0;
for0(i, m){
forn(j, idx, t - 1){
if(tamanio[j].s < robot2[i]){
if(!usados[tamanio[j].idx]){
pq.push({tamanio[j].idx, tamanio[j].w});
}
idx ++;
continue;
}
break;
}
cant += min((int) pq.size(), aux);
int aux2 = (int) pq.size();
for0(i, min(aux2, aux)){
ura2 act = pq.top();
usados[act.pos] = 1;
pq.pop();
}
}
return (cant == t);
}
int bs(){
int li = 1, ls = t, mitad, res = 0;
while(li <= ls){
mitad = (li + ls) / 2;
if(probar(mitad)){
res = mitad;
ls = mitad - 1;
}
else{
li = mitad + 1;
}
}
return res;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = A;
m = B;
for0(i, n){
robot1[i] = X[i];
}
sort(robot1, robot1 + n);
for0(i, m){
robot2[i] = Y[i];
}
sort(robot2, robot2 + m);
t = T;
for0(i, t){
peso[i] = {W[i], S[i], i};
tamanio[i] = peso[i];
}
sort(peso, peso + t, ordena1);
sort(tamanio, tamanio + t, ordena2);
return bs();
}
