#include "teams.h"
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class F> struct RecLambda : private F {
explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct Node {
int count, left, right;
Node() : count(0), left(0), right(0) {}
};
vector<Node> node = {Node()};
int size;
vector<int> roots;
int copy_node(const int k) {
node.push_back(node[k]);
return (int)node.size() - 1;
}
int add(const int k, const int i) {
return RecLambda([&](auto&& dfs, const int n, const int a, const int b) -> int {
const int u = copy_node(n);
if (a + 1 == b) {
node[u].count += 1;
} else {
const int m = (a + b) / 2;
if (i < m) {
node[u].left = dfs(node[u].left, a, m);
} else {
node[u].right = dfs(node[u].right, m, b);
}
node[u].count = node[node[u].left].count + node[node[u].right].count;
}
return u;
})(k, 0, size + 1);
}
int fold(const int k, const int l, const int r) {
return RecLambda([&](auto&& dfs, const int n, const int a, const int b) -> int {
if (l <= a and b <= r) return node[n].count;
if (b <= l or r <= a) return 0;
const int m = (a + b) / 2;
return dfs(node[n].left, a, m) + dfs(node[n].right, m, b);
})(k, 0, size + 1);
}
int rect(const int l, const int r, const int d, const int u) {
return fold(roots[r], d, u) - fold(roots[l], d, u);
}
void init(int N, int A[], int B[]) {
size = N;
vector<vector<int>> list(size + 1);
for (int i = 0; i < N; ++i) {
list[A[i]].push_back(B[i]);
}
int id = 0;
roots.push_back(id);
for (int x = 1; x <= N; ++x) {
for (const int y : list[x]) {
id = add(id, y);
}
roots.push_back(id);
}
}
int can(int M, int K[]) {
std::sort(K, K + M);
struct Point {
int x, y, c;
};
vector<Point> pts = {Point{0, size, 0}};
for (int i = 0; i < M; ++i) {
while (pts.back().y < K[i]) {
pts.pop_back();
}
int xr = K[i], cr = rect(pts.back().x, K[i], 0, K[i]);
while (true) {
const auto [xl, yl, cl] = pts.back();
if (rect(xl, xr, 0, yl + 1) - cr < K[i]) {
if (xl == 0) return false;
cr += cl;
pts.pop_back();
} else {
int left = 0, right = size + 1, sum = 0;
int u = roots[xr], v = roots[xl];
while (right - left > 1) {
const int add = node[node[u].left].count - node[node[v].left].count;
if (sum + add - cr < K[i]) {
sum += add;
left = (left + right) / 2;
u = node[u].right;
v = node[v].right;
} else {
right = (left + right) / 2;
u = node[u].left;
v = node[v].left;
}
}
pts.push_back(Point{xr, left, cr + K[i]});
break;
}
}
}
return true;
}
