#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
const int MAXN = 1e5 + 25;
const int SZE = 400;
int n;
array <int, 2> a[MAXN];
struct SegmentTree {
int tree[MAXN << 5], tl[MAXN << 5], tr[MAXN << 5];
int cnt;
int new_node (int x, int y) {
++cnt; tl[cnt] = x; tr[cnt] = y;
tree[cnt] = tree[x] + tree[y];
return cnt;
}
int build (int l, int r) {
if (l == r) {
return ++cnt;
}
return new_node(build(l, mid), build(mid + 1, r));
}
int update (int l, int r, int a, int b, int node) {
if (l == r) {
cnt++; tree[cnt] = tree[node] + b;
return cnt;
}
if (a <= mid) {
return new_node(update(l, mid, a, b, tl[node]), tr[node]);
} else {
return new_node(tl[node], update(mid + 1, r, a, b, tr[node]));
}
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
return get(l, mid, a, b, tl[node]) + get(mid + 1, r, a, b, tr[node]);
}
} cur;
vector <int> upd[MAXN];
int roots[MAXN];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++) {
a[i][0] = A[i];
}
for (int i = 0; i < n; i++) {
a[i][1] = B[i];
}
sort(a, a + n);
roots[0] = cur.build(1, n);
for (int i = 0; i < n; i++) {
upd[a[i][0]].push_back(a[i][1]);
}
for (int i = 1; i <= n; i++) {
roots[i] = roots[i - 1];
for (auto j : upd[i]) {
roots[i] = cur.update(1, n, j, 1, roots[i]);
}
}
}
vector <array <int, 3>> ee[MAXN];
int query (int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return 0;
return cur.get(1, n, y1, y2, roots[x2]) - cur.get(1, n, y1, y2, roots[x1 - 1]);
}
int can (int m, int k[]) {
int sum = 0;
for (int i = 0; i < m; i++) {
sum += k[i];
if (sum > n) {
return 0;
}
}
sort(k, k + m);
if (m >= SZE) {
for (int i = 1; i <= n; i++) {
ee[i].clear();
}
for (int i = 0; i < n; i++) {
ee[a[i][0]].push_back({a[i][1], i, 1});
ee[a[i][1] + 1].push_back({a[i][1], i, -1});
}
int ptr = 1;
set <array <int, 2>> cur;
for (int i = 0; i < m; i++) {
while (ptr <= k[i]) {
for (auto j : ee[ptr]) {
if (j[2] == 1) {
cur.insert({j[0], j[1]});
} else {
cur.erase({j[0], j[1]});
}
}
ptr++;
}
if (cur.size() < k[i]) {
return 0;
}
for (int j = 0; j < k[i]; j++) {
cur.erase(cur.begin());
}
}
return 1;
}
long long dp[m] = {};
for (int i = 0; i < m; i++) {
dp[i] = query(1, k[i], k[i], n);
for (int j = 0; j < i; j++) {
dp[i] = min(dp[i], dp[j] + query(k[j] + 1, k[i], k[i], n));
}
dp[i] -= k[i];
}
return *min_element(dp, dp + m) >= 0;
}
