#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 20;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
void compress (vector<int> &v) {
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
int A, B, N;
int X[MAXN], Y[MAXN], W[MAXN], S[MAXN];
vector<int> twei, tsiz;
struct segtree {
pii tree[2 * MAXN];
multiset<int> st[MAXN]; //f(v1) = v2
void init() {
for (int i = 0; i < MAXN; i++) {
tree[i + MAXN] = pii((st[i].empty() ? -1 : *st[i].rbegin()), i);
}
for (int i = MAXN - 1; i; i--) {
tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}
}
void update (int x, int v) {
tree[x += MAXN].fi = v;
while (x >>= 1) {
tree[x] = max(tree[x << 1], tree[(x << 1) | 1]);
}
}
void remove (int x, int y) {
auto it = st[x].find(y);
assert(it != st[x].end());
st[x].erase(it);
update(x, (st[x].empty() ? -1 : *st[x].rbegin()));
}
pii query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return pii(-1, -1);
}
if (a <= lt && rt <= b) {
return tree[cur];
}
int mid = (lt + rt) / 2;
return max(query(a, b, (cur << 1), lt, mid), query(a, b, ((cur << 1) | 1), mid, rt));
}
};
segtree segws, segsw; //f(w) = s, f(s) = w
int putaway (int aaa, int bbb, int nnn, int xxx[], int yyy[], int www[], int sss[]) {
A = aaa;
B = bbb;
N = nnn;
for (int i = 0; i < A; i++) {
X[i] = xxx[i];
}
for (int i = 0; i < B; i++) {
Y[i] = yyy[i];
}
for (int i = 0; i < N; i++) {
W[i] = www[i];
S[i] = sss[i];
twei.push_back(W[i]);
tsiz.push_back(S[i]);
}
compress(twei);
compress(tsiz);
for (int i = 0; i < A; i++) {
X[i] = lower_bound(all(twei), X[i]) - twei.begin();
}
for (int i = 0; i < B; i++) {
Y[i] = lower_bound(all(tsiz), Y[i]) - tsiz.begin();
}
sort(X, X + A);
sort(Y, Y + B);
for (int i = 0; i < N; i++) {
W[i] = lower_bound(all(twei), W[i]) - twei.begin();
S[i] = lower_bound(all(tsiz), S[i]) - tsiz.begin();
if (W[i] >= X[A - 1] && S[i] >= Y[B - 1]) {
return -1;
}
segws.st[W[i]].insert(S[i]);
segsw.st[S[i]].insert(W[i]);
//debug("(%d, %d)\n", W[i], S[i]);
}
// debug("TWEI:"); for (int i : twei) debug(" %d", i); debug("\n");
// debug("TSIZ:"); for (int i : tsiz) debug(" %d", i); debug("\n");
segws.init();
segsw.init();
int rescued = 0;
int ans = 0;
while (rescued < N) {
for (int i = 0; i < A; i++) {
//debug("X[i] = %d\n", X[i]);
pii p = segws.query(0, X[i]);
if (p.fi >= 0) {
//debug("A remove weight = %d, size = %d\n", twei[p.se], tsiz[p.fi]);
segws.remove(p.se, p.fi);
segsw.remove(p.fi, p.se);
rescued++;
}
}
for (int i = 0; i < B; i++) {
pii p = segsw.query(0, Y[i]);
if (p.fi >= 0) {
//debug("B remove weight = %d, size = %d\n", twei[p.fi], tsiz[p.se]);
segsw.remove(p.se, p.fi);
segws.remove(p.fi, p.se);
rescued++;
}
}
ans++;
}
return ans;
}
