#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int l, r, val, idx;
node *left, *right;
};
node *update(node *cur, int x, int val);
node *propagate(node *cur, int x, int val) {
if (x <= (cur->l + cur->r) / 2) {
node *left = cur->left;
if (left == nullptr) left = new node{cur->l, (cur->l + cur->r) / 2, 0, -1, nullptr, nullptr};
left = update(left, x, val);
return new node{cur->l, cur->r, 0, -1, left, cur->right};
} else {
node *right = cur->right;
if (right == nullptr) right = new node{(cur->l + cur->r) / 2 + 1, cur->r, 0, -1, nullptr, nullptr};
right = update(right, x, val);
return new node{cur->l, cur->r, 0, -1, cur->left, right};
}
}
node *update(node *cur, int x, int val) {
if (cur->l == cur->r) {
return new node{cur->l, cur->r, cur->val + val, cur->idx, nullptr, nullptr};
}
if (cur->idx == x) {
assert(cur->left == nullptr && cur->right == nullptr);
return new node{cur->l, cur->r, cur->val + val, cur->idx, nullptr, nullptr};
} else if (cur->idx != -1) {
cur = propagate(cur, cur->idx, cur->val);
cur->idx = -1;
} else if (cur->val == 0) {
assert(cur->left == nullptr && cur->right == nullptr);
return new node{cur->l, cur->r, val, x, nullptr, nullptr};
}
cur = propagate(cur, x, val);
cur->val = (cur->left != nullptr ? cur->left->val : 0) + (cur->right != nullptr ? cur->right->val : 0);
return cur;
}
int query(node *cur, int l, int r) {
if (l > r) return 0;
if (l <= cur->l && cur->r <= r) return cur->val;
if (cur->l > r || cur->r < l) return 0;
if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r ? cur->val : 0);
int ans = 0;
if (cur->left != nullptr) ans += query(cur->left, l, r);
if (cur->right != nullptr) ans += query(cur->right, l, r);
return ans;
}
int n;
vector<node*> root;
void init(int N, int A[], int B[]) {
n = N;
vector< pair<int, int> > v(n);
for (int i = 0; i < n; i++) v[i].first = A[i], v[i].second = B[i];
sort(v.begin(), v.end());
root.resize(n + 1); root[0] = new node{1, n, 0, -1, nullptr, nullptr};
for (int i = 1, j = 0; i <= n; i++) {
root[i] = root[i - 1];
while (j < N && v[j].first == i) root[i] = update(root[i], v[j++].second, +1);
}
}
int can(int M, int K[]) {
if (accumulate(K, K + M, 0ll) > n) return 0;
sort(K, K + M);
vector<int> used(M, 0);
for (int i = 0; i < M; i++) {
int left = K[i], ptr = i;
while (ptr < M) {
int cnt = query(root[K[i]], K[ptr], ptr < M - 1 ? K[ptr + 1] - 1 : n) - used[ptr];
used[ptr] += min(cnt, left);
left -= min(cnt, left);
if (left <= 0) break;
ptr++;
}
if (ptr == M && left > 0) return 0;
}
return 1;
}
