#include "robots.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXAB = 50000 + 10;
int n;
int w[MAXN];
int s[MAXN];
struct SegmentTree
{
int tree[4*MAXN];
std::bitset <MAXN> active;
int perm[MAXN];
bool type;
int cmp(const int &x, const int &y)
{
if (!active[x]) return y;
if (!active[y]) return x;
if (type)
{
if (w[perm[x]] > w[perm[y]]) return x;
return y;
} else
{
if (s[perm[x]] > s[perm[y]]) return x;
return y;
}
}
void build(int l, int r, int node)
{
if (l == r)
{
tree[node] = l;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryIdx)
{
if (l == r)
{
active[l] = 0;
return;
}
int mid = (l + r) / 2;
if (queryIdx <= mid) update(l, mid, 2*node, queryIdx);
else update(mid + 1, r, 2*node + 1, queryIdx);
tree[node] = cmp(tree[2*node], tree[2*node + 1]);
}
int query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res = cmp(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = cmp(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void build(bool _type)
{
type = _type;
active.set();
build(1, n, 1);
}
void update(int idx)
{
update(1, n, 1, idx);
}
int query(int x)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (type && s[perm[mid]] <= x) l = mid;
else if (!type && w[perm[mid]] <= x) l = mid;
else r = mid;
}
// std::cout << "queryTO: " << l << '\n';
if (l == 0) return 0;
return query(1, n, 1, 1, l);
}
};
int a, b;
int revX[MAXN];
int revY[MAXN];
SegmentTree sortedX;
SegmentTree sortedY;
int check(int times, int X[], int Y[])
{
sortedX.build(false);
sortedY.build(true);
int cntDestroyed = 0;
for (int curr = 1 ; curr <= a ; ++curr)
{
for (int t = 1 ; t <= times ; ++t)
{
int destroy = sortedX.query(X[curr - 1]);
// std::cout << "oblitarateX: " << destroy << ' ' << w[sortedX.perm[destroy]] << ' ' << s[sortedX.perm[destroy]] << ' ' << X[curr - 1] << '\n';
if (destroy == 0)
{
break;
} else
{
cntDestroyed++;
sortedX.update(destroy);
sortedY.update(revY[sortedX.perm[destroy]]);
}
}
}
for (int curr = 1 ; curr <= b ; ++curr)
{
for (int t = 1 ; t <= times ; ++t)
{
int destroy = sortedY.query(Y[curr - 1]);
// std::cout << "oblitarateY: " << destroy << ' ' << w[sortedY.perm[destroy]] << ' ' << s[sortedY.perm[destroy]] << ' ' << Y[curr - 1] << '\n';
if (destroy == 0)
{
break;
} else
{
cntDestroyed++;
sortedY.update(destroy);
sortedX.update(revY[sortedX.perm[destroy]]);
}
}
}
return cntDestroyed == n;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
a = A;
b = B;
n = T;
for (int i = 1 ; i <= n ; ++i)
{
w[i] = W[i - 1] + 1;
s[i] = S[i - 1] + 1;
}
std::iota(sortedX.perm + 1, sortedX.perm + 1 + n, 1);
std::sort(sortedX.perm + 1, sortedX.perm + 1 + n, [&](const int &a, const int &b)
{
return w[a] < w[b];
});
for (int i = 1 ; i <= n ; ++i)
{
revX[sortedX.perm[i]] = i;
}
std::iota(sortedY.perm + 1, sortedY.perm + 1 + n, 1);
std::sort(sortedY.perm + 1, sortedY.perm + 1 + n, [&](const int &a, const int &b)
{
return s[a] < s[b];
});
for (int i = 1 ; i <= n ; ++i)
{
revY[sortedY.perm[i]] = i;
}
std::sort(X, X + a);
std::sort(Y, Y + b);
// std::cout << "byW\n";
// for (int i = 1 ; i <= n ; ++i)
// {
// std::cout << w[sortedX.perm[i]] << ' ' << s[sortedX.perm[i]] << '\n';
// }
// std::cout << "byS\n";
// for (int i = 1 ; i <= n ; ++i)
// {
// std::cout << w[sortedY.perm[i]] << ' ' << s[sortedY.perm[i]] << '\n';
// }
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (!check(mid, X, Y)) l = mid;
else r = mid;
}
// check(3, X, Y);
if (r == n + 1) return -1;
return r;
}
