#include "robots.h"
#include <algorithm>
#include <queue>
#include <functional>
#define N 1000001
#define max2(x,y) (x>y?x:y)
using namespace std;
int len_a, len_b, len_toy, pass_len;
int A[50001], B[50001], pass[N];
pair<int, int> toy[N];
priority_queue<int,vector<int>,greater<int> > Q;
bool Can(int max_size) {
int k = len_a, r_size = 0;
pass_len = 0;
while (!Q.empty()) Q.pop();
for (int i = len_toy; i >= 1; i--) {
while (toy[i].first <= A[k]) k--, r_size += max_size;
r_size--, Q.push(toy[i].second);
if (r_size < 0) pass[++pass_len] = Q.top(), Q.pop(), r_size++;
}
sort(pass + 1, pass + pass_len + 1);
k = len_b + 1, r_size = 0;
for (int i = pass_len; i >= 1; i--) {
if (!r_size) k--, r_size = max_size;
if (!k) return false;
if (pass[i] > B[k]) return false;
r_size--;
}
return true;
}
int putaway(int _la, int _lb, int _lt, int _A[], int _B[], int in1[], int in2[]) {
int A_MAX = 0, B_MAX = 0;
len_a = _la, len_b = _lb, len_toy = _lt;
for (int i = 0; i < len_a; i++) A[i + 1] = _A[i] - 1, A_MAX = max2(A_MAX, _A[i] - 1);
for (int i = 0; i < len_b; i++) B[i + 1] = _B[i] - 1, B_MAX = max2(B_MAX, _B[i] - 1);
for (int i = 0; i < len_toy; i++) {
toy[i + 1] = { in1[i],in2[i] };
if (in1[i] > A_MAX && in2[i] > B_MAX) return -1;
}
sort(toy + 1, toy + len_toy + 1);
sort(A + 1, A + len_a + 1), sort(B + 1, B + len_b + 1);
int l = 1, r = len_toy, mid;
while (l <= r) {
mid = (l + r) / 2;
if (Can(mid)) r = mid - 1;
else l = mid + 1;
}
return r + 1;
}
