#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
class MergeSortTree {
public:
int n;
vector<vector<int>> a;
void build(const vector<int>& data) {
n = data.size();
a.resize(4 * n);
build(1, 0, n, data);
}
void build(int v, int vl, int vr, const vector<int>& data) {
if(vr - vl == 1) {
a[v].push_back(data[vl]);
} else {
int vm = (vl + vr) / 2;
build(v * 2, vl, vm, data);
build(v * 2 + 1, vm, vr, data);
a[v].resize(vr - vl);
merge(a[v * 2].begin(), a[v * 2].end(), a[v * 2 + 1].begin(), a[v * 2 + 1].end(), a[v].begin());
}
}
int cnt_in_range(int v, int vl, int vr, int l, int r, int low, int high) {
if(vl == l && vr == r) {
return lower_bound(a[v].begin(), a[v].end(), high) - lower_bound(a[v].begin(), a[v].end(), low);
}
int vm = (vl + vr) / 2;
if(r <= vm) {
return cnt_in_range(v * 2, vl, vm, l, r, low, high);
} else if(l >= vm) {
return cnt_in_range(v * 2 + 1, vm, vr, l, r, low, high);
} else {
return cnt_in_range(v * 2, vl, vm, l, vm, low, high) + cnt_in_range(v * 2 + 1, vm, vr, vm, r, low, high);
}
}
int cnt_in_range(int l, int r, int low, int high) {
if(l == r || low >= high) {
return 0;
}
return cnt_in_range(1, 0, n, l, r, low, high);
}
int first_cnt_in_range(int v, int vl, int vr, int l, int r, int low, int high, int cnt) {
while(vr - vl > 1) {
int vm = (vl + vr) / 2;
if(r <= vm) {
v = v * 2;
vr = vm;
} else if(l >= vm) {
v = v * 2 + 1;
vl = vm;
} else {
int cnt_left = cnt_in_range(v * 2, vl, vm, l, vm, low, high);
if(cnt_left >= cnt) {
v = v * 2;
vr = vm;
r = vm;
} else {
cnt -= cnt_left;
v = v * 2 + 1;
vl = vm;
l = vm;
}
}
}
if(cnt == 0) {
return l;
} else {
assert(cnt == 1 && a[v][0] >= low && a[v][0] < high);
return r;
}
}
int first_cnt_in_range(int l, int r, int low, int high, int cnt) {
if(cnt == 0) {
return l;
}
return first_cnt_in_range(1, 0, n, l, r, low, high, cnt);
}
};
vector<pair<int, int>> students;
MergeSortTree students_first_mst;
void init(int n, int a[], int b[]) {
for(int i = 0; i < n; i++) {
students.emplace_back(a[i], b[i]);
}
sort(students.begin(), students.end(), [](pair<int, int> p1, pair<int, int> p2) {
return p1.second < p2.second;
});
vector<int> students_first(n);
for(int i = 0; i < n; i++) {
students_first[i] = students[i].first;
}
students_first_mst.build(students_first);
}
int can(int m, int k[]) {
sort(k, k + m);
long long total = 0;
for(int i = 0; i < m; i++) {
total += k[i];
}
if(total > students.size()) {
return 0;
}
multiset<pair<int, int>> disabled_intervals;
disabled_intervals.emplace(students.size(), 0);
for(int i = 0; i < m; i++) {
int l = lower_bound(students.begin(), students.end(), make_pair(0, k[i]), [](pair<int, int> p1, pair<int, int> p2) {
return p1.second < p2.second;
}) - students.begin();
if(l == students.size()) {
return 0;
}
while(disabled_intervals.begin()->first <= l) {
disabled_intervals.erase(disabled_intervals.begin());
}
int cnt = 0;
int r = l;
while(!disabled_intervals.empty()) {
auto [r1, x] = *disabled_intervals.begin();
// search in range r..r1
int cnt_in_range = students_first_mst.cnt_in_range(r, r1, x + 1, k[i] + 1);
if(cnt + cnt_in_range < k[i]) {
// Have to take the whole range
cnt += cnt_in_range;
r = r1;
disabled_intervals.erase(disabled_intervals.begin());
} else {
// This range is certainly enough to finish the project
r = students_first_mst.first_cnt_in_range(r, r1, x + 1, k[i] + 1, k[i] - cnt);
cnt = k[i];
if(r == r1) {
disabled_intervals.erase(disabled_intervals.begin());
}
break;
}
}
if(cnt < k[i]) {
return 0;
}
disabled_intervals.insert(make_pair(r, k[i]));
}
return 1;
}
