#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MX_N = 500042;
int n;
pair<int, int> stud[MX_N];
vector<int> startAt[MX_N];
int bit[MX_N];
int tree[42 * MX_N], lc[42 * MX_N], rc[42 * MX_N], roots[MX_N];
int nxtIdx = 1;
void add(int idx, int val) {
for (++idx; idx < MX_N; idx += (idx & -idx))
bit[idx] += val;
}
int getPref(int idx) {
int ans = 0;
for (++idx; idx > 0; idx -= (idx & -idx))
ans += bit[idx];
return ans;
}
int getSum(int l, int r) {
return getPref(r) - getPref(l - 1);
}
void cpy(int& node) {
lc[nxtIdx] = lc[node];
rc[nxtIdx] = rc[node];
tree[nxtIdx] = tree[node];
node = nxtIdx++;
}
void upd(int& node, int cL, int cR, int qL, int qR, int val) {
if (cL > qR || cR < qL)
return;
cpy(node);
if (cL >= qL && cR <= qR) {
tree[node] += val;
return;
}
int mid = (cL + cR) / 2;
upd(lc[node], cL, mid, qL, qR, val);
upd(rc[node], mid + 1, cR, qL, qR, val);
tree[node] = tree[lc[node]] + tree[rc[node]];
}
int getFirst(int node, int cL, int cR, int mnRight) {
if (cR < mnRight || !node)
return -1;
assert(tree[node] >= getSum(cL, cR));
if (tree[node] - getSum(cL, cR) == 0)
return -1;
if (cL == cR)
return cL;
int mid = (cL + cR) / 2;
int a = getFirst(lc[node], cL, mid, mnRight);
if (a != -1)
return a;
return getFirst(rc[node], mid + 1, cR, mnRight);
}
void init(int N, int A[], int B[]) {
for (int i = 0; i < N; i++) {
stud[i] = {A[i], B[i]};
startAt[A[i]].push_back(B[i]);
}
n = N;
for (int i = 1; i <= n; i++) {
roots[i] = roots[i - 1];
for (auto& x: startAt[i])
upd(roots[i], 1, n, x, x, 1);
}
}
int can(int M, int K[]) {
sort(K, K + M);
vector<int> toRem {};
for (int i = 0; i < M; i++) {
int req = K[i];
while (req) {
int id = getFirst(roots[K[i]], 1, n, K[i]);
if (id == -1)
break;
toRem.push_back(id);
add(id, 1);
req--;
}
if (req != 0)
return 0;
}
for (auto& x: toRem)
add(x, -1);
return 1;
}
