#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct dato{
int peso;
int altura;
int id;
};
bool compara(dato x, dato y){
if(x.altura == y.altura){
return x.peso < y.peso;
}
return x.altura < y.altura;
}
bool compara2(dato x, dato y){
if(x.peso == y.peso){
return x.altura < y.altura;
}
return x.peso < y.peso;
}
int color;
int visitado[1000002];
dato jugPeso[1000002];
dato jugAlt[1000002];
int roboA[50002];
int roboB[50002];
bool probar(int k, int n, int a, int b){
sort(jugPeso, jugPeso + n, compara2);
sort(jugAlt, jugAlt + n, compara);
sort(roboA, roboA + a);
sort(roboB, roboB + b);
bool ans = true;
priority_queue<pair<int, int> > colaP;
///el primero es la altura, el segundo es el id
priority_queue<pair<int, int> > colaP2;
/// el primero es el peso, el segundo es el id
int ind = 0;
for(int i = 0; i < a; ++i){
while(jugPeso[ind].peso < roboA[i] && ind < n){
colaP.push({jugPeso[ind].altura, jugPeso[ind].id});
ind++;
}
for(int j = 1; j <= k; ++j){
if(!colaP.empty()){
pair<int, int> sig;
sig = colaP.top();
colaP.pop();
visitado[sig.second] = color;
}else{
break;
}
}
}
ind = 0;
for(int i = 0; i < b; ++i){
while(jugAlt[ind].altura < roboB[i] && ind < n){
if(visitado[jugAlt[ind].id] != color){
colaP2.push({jugAlt[ind].peso, jugAlt[ind].id});
ind++;
}
}
for(int j = 1; j <= k; ++j){
if(!colaP2.empty()){
pair<int, int> sig;
sig = colaP2.top();
colaP2.pop();
visitado[sig.second] = color;
}else{
break;
}
}
}
for(int i = 0; i < n; ++i){
if(visitado[i] != color) ans = false;
}
return ans;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int ans = -1, medio, sup = T, inf = 1;
while(inf <= sup){
medio = (inf + sup) / 2;
for(int i = 0; i < T; ++i){
dato aux;
aux.id = i;
aux.peso = W[i];
aux.altura = S[i];
jugPeso[i] = aux;
jugAlt[i] = aux;
}
for(int i = 0; i < A; ++i){
roboA[i] = X[i];
}
for(int i = 0; i < B; ++i){
roboB[i] = Y[i];
}
color++;
if(probar(medio, T, A, B)){
ans = medio;
sup = medio - 1;
}else{
inf = medio + 1;
}
}
return ans;
}
