#include "robots.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <bitset>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXAB = 50000 + 10;
int n;
struct LinkedList
{
int prev[MAXAB];
int next[MAXAB];
void build(int sz)
{
for (int i = 0 ; i <= sz ; ++i)
{
prev[i] = i - 1;
next[i] = i + 1;
}
}
void erase(int idx)
{
next[prev[idx]] = next[idx];
prev[next[idx]] = prev[idx];
}
};
LinkedList byX;
LinkedList byY;
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[x] > w[y]) return x;
return y;
} else
{
if (s[x] > s[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 && w[mid] <= x) l = mid;
else if (!type && s[mid] <= x) l = mid;
else r = mid;
}
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 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 - 1] < W[b - 1];
});
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 - 1] < S[b - 1];
});
for (int i = 1 ; i <= n ; ++i)
{
revY[sortedY.perm[i]] = i;
}
sortedX.build(false);
sortedY.build(true);
std::sort(X, X + a);
std::sort(Y, Y + b);
for (int i = 1 ; i <= n ; ++i)
{
// std::cout << "here: " << w
if (w[i] > X[a - 1] && s[i] > Y[b - 1])
{
return -1;
}
}
byX.build(a);
byY.build(b);
int ans = 0;
int cntDestroyed = 0;
while (cntDestroyed < n)
{
ans++;
int curr = 0;
while (true)
{
curr = byX.next[curr];
if (curr == a + 1)
{
break;
}
int destroy = sortedX.query(X[curr - 1]);
if (destroy == 0)
{
byX.erase(curr);
} else
{
cntDestroyed++;
sortedX.update(sortedX.perm[destroy]);
sortedY.update(revY[sortedX.perm[destroy]]);
}
}
while (true)
{
curr = byY.next[curr];
if (curr == b + 1)
{
break;
}
int destroy = sortedY.query(Y[curr - 1]);
if (destroy == 0)
{
byY.erase(curr);
} else
{
cntDestroyed++;
sortedY.update(sortedY.perm[destroy]);
sortedX.update(revX[sortedY.perm[destroy]]);
}
}
}
return ans;
}
