#include <bits/stdc++.h>
#include "robots.h"
#define ii pair<int, int>
#define ar array<int, 3>
using namespace std;
bitset<1000001> mark;
vector<ii> v, item_w, item_s;
struct cmp{
bool operator() (const ar &a, const ar &b) const{
return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
}
};
bool check(int mid, int T, int X[], int Y[], int W[], int S[]){
for(int i = 0; i <= T; i++) mark[i] = 0;
priority_queue<ar, vector<ar>, cmp> wt, sz;
int idx_w = 0, idx_s = 0;
// printf("T = %d\n", mid);
for(auto [x, t] : v){
int cnt = 0;
if(t == 1){
while(idx_w < T && item_w[idx_w].first < x){
wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
idx_w++;
}
while(!wt.empty()){
auto [w, s, i] = wt.top();
wt.pop();
if(mark[i]) continue;
if(w >= x || cnt >= mid) break;
mark[i] = 1;
// printf("bot weak %d take %d (%d)\n", x, w, i);
cnt++;
}
}
else{
while(idx_s < T && item_s[idx_s].first < x){
sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
idx_s++;
}
while(!sz.empty()){
auto [s, w, i] = sz.top();
sz.pop();
if(mark[i]) continue;
if(s >= x || cnt >= mid) break;
mark[i] = 1;
// printf("bot small %d take %d (%d)\n", x, s, i);
cnt++;
}
}
}
while(idx_w < T){
wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
idx_w++;
}
while(idx_s < T){
sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
idx_s++;
}
while(!sz.empty() && mark[sz.top()[2]]) sz.pop();
while(!wt.empty() && mark[wt.top()[2]]) wt.pop();
return sz.empty() && wt.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for(int i = 0; i < A; i++) v.push_back({X[i], 1});
for(int i = 0; i < B; i++) v.push_back({Y[i], 2});
sort(v.begin(), v.end());
for(int i = 0; i < T; i++){
item_w.push_back({W[i], i});
item_s.push_back({S[i], i});
}
sort(item_w.begin(), item_w.end());
sort(item_s.begin(), item_s.end());
int l = 1, r = T; bool ans = false;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid, T, X, Y, W, S)){
ans = true;
r = mid;
}
else l = mid + 1;
}
if(check(l, T, X, Y, W, S)) ans = true;
if(!ans) return -1;
return l;
}
