#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f1 first
#define s2 second
using ii = pair<int, int>;
const int MAX = 5e4 + 69;
const int inf = 1e9 + 69;
struct Segtree
{
int n, st[1 << 17], lz[1 << 17];
Segtree() {}
Segtree (int n_, int ar[]) : n(n_)
{
memset(lz, 0, sizeof(lz));
const auto build = [&](const auto &self, int node, int l, int r) -> void
{
if (l == r)
{
st[node] = ar[l];
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = min(st[node << 1], st[node << 1 | 1]);
};
build(build, 1, 0, n-1);
}
inline void propagate(int node, int l, int r)
{
st[node] += lz[node];
if (l < r)
{
lz[node << 1] += lz[node];
lz[node << 1 | 1] += lz[node];
}
lz[node] = 0;
}
inline void add(int p, int q, int val)
{
const auto add_ = [&](const auto &self, int node, int l, int r) -> void
{
propagate(node, l, r);
if (l > q || r < p)
return;
if (p <= l && r <= q)
{
lz[node] += val;
propagate(node, l, r);
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = min(st[node << 1], st[node << 1 | 1]);
};
add_(add_, 1, 0, n-1);
}
inline int query(int p, int q)
{
const auto query_ = [&](const auto &self, int node, int l, int r) -> int
{
propagate(node, l, r);
if (l > q || r < p)
return inf;
if (p <= l && r <= q)
return st[node];
int mid = (l + r) >> 1;
return min(self(self, node << 1, l, mid), self(self, node << 1 | 1, mid+1, r));
};
return query_(query_, 1, 0, n-1);
}
} st;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
sort(X, X+A);
sort(Y, Y+B);
for (int i = 0; i < T; ++i)
{
if ((A == 0 || X[A-1] <= W[i]) && (B == 0 || Y[B-1] <= S[i]))
return -1;
}
vector<ii> vec;
for (int i = 0; i < T; ++i)
{
int p = (int)(upper_bound(Y, Y+B, S[i]) - Y);
int q = (int)(upper_bound(X, X+A, W[i]) - X);
vec.pb({p, q});
}
sort(vec.rbegin(), vec.rend());
int ar[MAX];
const auto check = [&](int val) -> bool
{
ar[A] = 0;
for (int i = A-1; i >= 0; --i)
ar[i] = min(inf, ar[i+1] + val);
st = Segtree(A+1, ar);
for (int i = 0; i <= B; ++i)
ar[i] = 0;
for (int i = 0; i < T; ++i)
{
if (st.query(0, vec[i].s2) > 0)
st.add(0, vec[i].s2, -1);
else ar[0]++, ar[vec[i].f1 + 1]--;
}
for (int i = 1; i <= B; ++i)
ar[i] += ar[i-1];
for (int i = 0; i <= B; ++i)
if (ar[i] > 1ll * (B-i) * val)
return false;
return true;
};
int l = 1, r = T;
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
