// ty gian ily
/*
using a pqueue this time (this is what i missed), we try to assign the weak robots in such a way that they take the HEAVIEST ones they can do for some count.
afterwards, we can just consider strong robots normally (backwards order).
*/
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
struct Toy{
int w, s, i; // almost in the thick of it
Toy(): w(-1), s(-1), i(-1) {};
Toy(int a, int b, int c): w(a), s(b), i(c) {};
};
bool vis[1000005];
vector<Toy> toysW;
vector<Toy> toysS;
vector<int> wLim;
vector<int> sLim;
struct Comp{
bool operator()(const Toy &a, const Toy &b) { // pqueue is in reverse, it should be false throughout
return a.w == b.w ? a.s > b.s : a.w < b.w;
}
};
bool check(int cnt, int &a, int &b, int &t) {
priority_queue<Toy, vector<Toy>, Comp> pq;
int left = t;
int sz = 0;
for(int i = 0, j = 0, rem = cnt; i < b; i++, rem = cnt) { // greedy on the small robots
while(j < t) {
if(toysS[j].s < sLim[i]) { // sorted by size, just keep going until we run out
pq.emplace(toysS[j]);
j++;
sz++;
} else break;
}
while(sz && rem) {
Toy item = pq.top(); pq.pop(); // were popping it anyways so it makes sense that we dont need to give a crap
vis[item.i] = true;
sz--; rem--; left--;
}
}
while(!pq.empty()) pq.pop(); // bye
sz = 0;
for(int i = 0, j = 0, rem = cnt; i < a; i++, rem = cnt) {
while(j < t) {
if(toysW[j].w < wLim[i]) { // sorted by size, just keep going until we run out
if(!vis[toysW[j].i]) {
pq.emplace(toysW[j]);
sz++;
}
j++;
} else break;
}
while(sz && rem) {
Toy item = pq.top(); pq.pop(); // were popping it anyways so it makes sense that we dont need to give a crap
vis[item.i] = true;
sz--; rem--; left--;
}
}
return left == 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for(int i = 0; i < T; i++) {
toysW.push_back(Toy(W[i], S[i], i));
toysS.push_back(Toy(W[i], S[i], i));
}
for(int i = 0; i < A; i++) {
wLim.push_back(X[i]);
}
for(int i = 0; i < B; i++) {
sLim.push_back(Y[i]);
}
sort(toysW.begin(), toysW.end(), [](const Toy &a, const Toy &b) {
return a.w == b.w ? a.s < b.s : a.w < b.w;
});
sort(toysS.begin(), toysS.end(), [](const Toy &a, const Toy &b) {
return a.s == b.s ? a.w < b.w : a.s < b.s;
});
sort(wLim.begin(), wLim.end(), less<int>());
sort(sLim.begin(), sLim.end(), less<int>());
int l = 0, r = T+1;
while(l + 1 < r) {
memset(vis, 0, sizeof(vis)); // illegal, but do i care? nah
int m = (l+r)>>1;
if(check(m, A, B, T)) { // its valid, add to set
r = m;
} else l = m;
}
if(r == T+1) return -1;
return r;
}
