#include "teams.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
const int B_SIZE = 750; // N.B. No less than 708
struct Node {
int val;
Node *l, *r;
Node(int x) : val(x), l(nullptr), r(nullptr) {}
Node(Node *ll, Node *rr) {
l = ll, r = rr;
val = 0;
if (l) val += l->val;
if (r) val += r->val;
}
Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {}
};
int n;
pair<int, int> s[500000], min_max[B_SIZE];
Node *orig, *curr;
Node *build(int l = 0, int r = n - 1) {
if (l == r) return new Node(1);
int mid = (l + r) / 2;
return new Node(build(l, mid), build(mid + 1, r));
}
Node *update(Node *node, int a, int b, int l = 0, int r = n - 1) {
if (l > b || r < a) return node;
if (l >= a && r <= b) return new Node(0);
int mid = (l + r) / 2;
return new Node(update(node->l, a, b, l, mid), update(node->r, a, b, mid + 1, r));
}
int query(Node *node, int a, int b, int l = 0, int r = n - 1) {
if (!node->val || l > a || r < b) return 0;
if (l >= a && r <= b) return node->val;
int mid = (l + r) / 2;
return query(node->l, a, b, l, mid) + query(node->r, a, b, mid + 1, r);
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++) s[i] = {A[i], B[i]};
sort(s, s + n, [](pair<int, int> X, pair<int, int> Y) {
return X.second < Y.second;
});
for (int i = 0; i < n; i += B_SIZE) {
sort(s + i, s + min(n, i + B_SIZE));
min_max[i / B_SIZE] = {INT_MAX, INT_MIN};
}
for (int i = 0; i < n; i++) {
min_max[i / B_SIZE].first =
min(min_max[i / B_SIZE].first, s[i].second);
min_max[i / B_SIZE].second =
max(min_max[i / B_SIZE].second, s[i].second);
}
orig = build();
}
int can(int M, int K[]) {
sort(K, K + M);
curr = new Node(orig);
for (int i = 0; i < M; i++) {
int cnt = 0;
for (int j = 0; j < n; j += B_SIZE) {
if (min_max[j / B_SIZE].first < K[i] && min_max[j / B_SIZE].second < K[i]) {
continue;
} else if (min_max[j / B_SIZE].first < K[i] && min_max[j / B_SIZE].second >= K[i]) {
for (int k = j; k < j + B_SIZE && cnt != K[i]; k++) {
if (s[k].first <= K[i] && s[k].second >= K[i] && query(curr, k, k)) {
cnt++;
curr = update(curr, k, k);
}
}
if (cnt == K[i]) break;
} else {
int idx = upper_bound(s + j, s + min(n, j + B_SIZE), make_pair(K[i], INT_MAX)) - s - j - 1;
int available = query(curr, j, idx);
if (cnt + available < K[i]) {
cnt += available;
curr = update(curr, j, idx);
} else {
for (int k = j; k < j + B_SIZE && cnt != K[i]; k++) {
if (query(curr, k, k)) {
cnt++;
curr = update(curr, k, k);
}
}
break;
}
}
}
if (cnt != K[i]) return 0;
}
return 1;
}
