#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
static int A, B, T;
static int robot1[50009], robot2[50009];
static pair<int,int> toys[1000009];
// segment tree
static pair<int,int> st[4000009];
void reset(int id,int l,int r) {
st[id] = {0,0};
if (l == r) return;
int mid = (l + r) >> 1;
reset(id*2,l,mid);
reset(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int pos,int val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id] = {val,l};
return;
}
int mid = (l + r) >> 1;
update(id*2,l,mid,pos,val);
update(id*2+1,mid+1,r,pos,val);
st[id] = max(st[id*2],st[id*2 + 1]);
}
pair<int,int> get(int id,int l,int r) {
if (l == r) return st[id];
int mid = (l + r) >> 1;
if (st[id*2] > st[id*2 + 1]) return get(id*2,l,mid);
return get(id*2+1,mid+1,r);
}
bool check(int lim) {
reset(1,1,T);
int pt = 0;
// Phase 1: robots yếu
for (int i = 1; i <= A; i++) {
while (pt < T && toys[pt + 1].first <= robot1[i]) {
pt++;
update(1,1,T,pt,toys[pt].second);
}
for (int j = 1; j <= lim; j++) {
pair<int,int> dd = get(1,1,T);
if (dd.first == 0) break;
update(1,1,T,dd.second,0);
}
}
while (pt < T) {
pt++;
update(1,1,T,pt,toys[pt].second);
}
// Phase 2: robots nhỏ
priority_queue<int,vector<int>,greater<int>> leftover;
while (true) {
pair<int,int> dd = get(1,1,T);
if (dd.first == 0) break;
update(1,1,T,dd.second,0);
leftover.push(dd.first);
}
for (int i = 1; i <= B; i++) {
for (int j = 1; j <= lim; j++) {
if (leftover.empty() || leftover.top() > robot2[i]) break;
leftover.pop();
}
}
return leftover.empty();
}
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 = 1; i <= A; i++) robot1[i] = X[i-1];
for (int i = 1; i <= B; i++) robot2[i] = Y[i-1];
for (int i = 1; i <= T; i++) {
toys[i].first = W[i-1] + 1;
toys[i].second = S[i-1] + 1;
}
sort(robot1 + 1, robot1 + 1 + A);
sort(robot2 + 1, robot2 + 1 + B);
sort(toys + 1, toys + 1 + T);
int l = 1, r = T, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
