#include "robots.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e6 + 1e5 + 100;
struct bit {
int bit[N];
void clear() {
memset(bit, 0, sizeof bit);
}
void add(int pos, int val) {
for(; pos < N; pos += pos & -pos)
bit[pos] += val;
}
int psum(int pos) {
int res = 0;
for(; pos; pos -= pos & -pos)
res += bit[pos];
return res;
}
int qry(int i) {
int want = psum(i), s = 0, now = 0;
for(int j = 20; j >= 0; j--) {
if(s + (1 << j) < N && now + bit[s + (1 << j)] <= want) {
now += bit[s + (1 << j)];
s += 1 << j;
}
}
if(s == N - 1) return -1;
assert(psum(s + 1) > want);
return s + 1;
}
} bit1, bit2;
int putaway(int A, int B, int T, int a[], int b[], int W[], int S[]) {
sort(a, a + A), sort(b, b + B);
vi p(T);
iota(ALL(p), 0);
sort(ALL(p), [&] (int a, int b) {
return S[a] < S[b];
});
vi compress;
for(int i = 0; i < A; i++) compress.PB(a[i]);
for(int i = 0; i < B; i++) compress.PB(b[i]);
for(int i = 0; i < T; i++) compress.PB(W[i]), compress.PB(S[i]);
sort(ALL(compress));
compress.resize(unique(ALL(compress)) - compress.begin());
auto go = [&] (int x) {
return lower_bound(ALL(compress), x) - compress.begin() + 1;
};
assert(int(compress.size()) < N);
for(int i = 0; i < A; i++) a[i] = go(a[i]);
for(int i = 0; i < B; i++) b[i] = go(b[i]);
for(int i = 0; i < T; i++) W[i] = go(W[i]);
for(int i = 0; i < T; i++) S[i] = go(S[i]);
auto ok = [&] (int k) { // each people can kill at msot k things
bit1.clear();
bit2.clear();
int tt = T;
for(int i = A - 1; i >= 0 && tt > 0; i--) {
bit1.add(a[i], k);
tt -= k;
}
tt = T;
for(int i = B - 1; i >= 0 && tt > 0; i--) {
bit2.add(b[i], k);
tt -= k;
}
bool ok = true;
for(int i = T - 1; i >= 0; i--) {
int x = W[p[i]], y = S[p[i]];
int pos = bit1.qry(x);
if(pos != -1) {
bit1.add(pos, -1);
} else {
int pos = bit2.qry(y);
if(pos == -1) return false;
bit2.add(pos, -1);
}
}
return true;
};
int lb = 1, rb = T;
while(lb <= rb) {
int mb = (lb + rb) / 2;
if(ok(mb)) rb = mb - 1;
else lb = mb + 1;
}
if(lb > T) return -1;
return lb;
}
