#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define lc(v) (v * 2)
#define rc(v) (v * 2 + 1)
#define mid (l + r) / 2
#define ff first
#define ss second
const int N = 1e6;
class seg_tree {
pair<int, int> t[N * 4];
void build(int v, int l, int r, pair<int, int> a[]) {
if (l == r) {
t[v] = {a[l].ss, a[l].ff};
return;
}
build(lc(v), l, mid, a);
build(rc(v), mid + 1, r, a);
t[v] = max(t[lc(v)], t[rc(v)]);
}
public:
seg_tree(int n, pair<int, int> a[]) {
build(1, 0, n - 1, a);
}
pair<int, int> query(int v, int l, int r, int tl, int tr) {
if (tl > tr)
return {-1, -1};
else if (l == tl && r == tr)
return t[v];
return max(query(lc(v), l, mid, tl, min(mid, tr)), query(rc(v), mid + 1, r, max(tl, mid + 1), tr));
}
void update(int v, int l, int r, int tl) {
if (l == r && l == tl) {
t[v] = {-1, -1};
return;
}
if (tl <= mid)
update(lc(v), l, mid, tl);
else
update(rc(v), mid + 1, r, tl);
t[v] = max(t[lc(v)], t[rc(v)]);
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
pair<int, int> t1[T], t2[T];
multiset<int> x, y;
for (int i = 0; i < T; i++) {
t1[i] = {W[i], S[i]};
t2[i] = {S[i], W[i]};
x.insert(W[i]);
y.insert(S[i]);
}
sort(t1, t1 + T);
sort(t2, t2 + T);
sort(X, X + A);
sort(Y, Y + B);
if ((t1[T - 1].ff >= X[A - 1] && t1[T - 1].ss >= Y[B - 1]) || (t2[T - 1].ff >= Y[B - 1] && t2[T - 1].ss >= X[A - 1]))
return -1;
multimap<pair<int, int>, int> m1, m2;
for (int i = 0; i < T; i++) {
m1.insert({t1[i], i});
m2.insert({t2[i], i});
}
seg_tree st1(T, t1), st2(T, t2);
int ans = 0, done = 0;
while (done != T) {
ans++;
int p = upper_bound(X, X + A, *x.begin()) - X;
while (p != A && done != T) {
pair<int, int> q = st1.query(1, 0, T - 1, 0, lower_bound(t1, t1 + T, pair<int, int>{X[p] - 1, 1e9}) - t1 - 1);
auto itr = m1.find({q.ss, q.ff});
st1.update(1, 0, T - 1, itr->ss);
m1.erase(itr);
itr = m2.find(q);
st2.update(1, 0, T - 1, itr->ss);
m2.erase(itr);
x.erase(x.find(q.ss));
y.erase(y.find(q.ff));
done++;
int p_ = upper_bound(X, X + A, *x.begin()) - X;
p = max(p + 1, p_);
}
p = upper_bound(Y, Y + B, *y.begin()) - Y;
while (p != B && done != T) {
pair<int, int> q = st2.query(1, 0, T - 1, 0, lower_bound(t2, t2 + T, pair<int, int>{Y[p] - 1, 1e9}) - t2 - 1);
auto itr = m2.find({q.ss, q.ff});
st2.update(1, 0, T - 1, itr->ss);
m2.erase(itr);
itr = m1.find(q);
st1.update(1, 0, T - 1, itr->ss);
m1.erase(itr);
y.erase(y.find(q.ss));
x.erase(x.find(q.ff));
done++;
int p_ = upper_bound(Y, Y + B, *y.begin()) - Y;
p = max(p + 1, p_);
}
}
return ans;
}
