#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 500001, N_ = (N + 400001) * 19;
int cnt[N_ + 1], L[N_ + 1], R[N_ + 1], sz = 1, root[N];
int create(int val, int l, int r) {
int x = sz++;
cnt[x] = val, L[x] = l, R[x] = r;
return x;
}
int modify(int x, int lx, int rx, int i) {
int nx = create(cnt[x] + 1, L[x], R[x]);
if (lx + 1 < rx) {
int mid = (lx + rx) >> 1;
if (i < mid) {
L[nx] = modify(L[x], lx, mid, i);
} else {
R[nx] = modify(R[x], mid, rx, i);
}
}
return nx;
}
int n;
void init(int n_, int A[], int B[]) {
n = n_;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return A[i] < A[j];
});
int j = 0, x = 0;
for (int i = 0; i <= n; ++i) {
while (j < n && A[ord[j]] == i) {
x = modify(x, 0, n, B[ord[j++]] - 1);
}
root[i] = x;
}
}
int query(int x, int u, int lx, int rx, int i, int &k) {
if (rx <= i || k == 0) return u;
if (lx >= i && k >= cnt[x] - cnt[u]) {
k -= cnt[x] - cnt[u];
return x;
}
int mid = (lx + rx) >> 1;
int nu = sz++;
if (lx + 1 < rx) {
L[nu] = query(L[x], L[u], lx, mid, i, k);
R[nu] = query(R[x], R[u], mid, rx, i, k);
cnt[nu] = cnt[L[nu]] + cnt[R[nu]];
} else {
cnt[nu] = cnt[u] + k;
k = 0;
}
return nu;
}
int can(int m, int K[]) {
if (accumulate(K, K + m, 0ll) > n) {
return 0;
}
sort(K, K + m);
int used = 0;
for (int i = 0; i < m; ++i) {
int k = K[i];
used = query(root[k], used, 0, n, k - 1, k);
if (k > 0) {
return 0;
}
}
return 1;
}
