#include "teams.h"
#include <bits/stdc++.h>
struct Seg {
struct Item {
int val = 0, l = 0, r = 0;
};
int size;
std::vector <Item> v;
Seg() : size(1), v(1, Item()) { }
int update(int ind, int now, int l, int r) {
int nv = size++;
v.push_back(Item());
v[nv].val = v[now].val;
if (!(r - l - 1)) {
v[nv].val++;
return nv;
}
if (!v[now].l) {
v[now].l = size++;
v[now].r = size++;
v.resize(v.size() + 2, Item());
}
v[nv].l = v[now].l;
v[nv].r = v[now].r;
int mid = (l + r) >> 1;
if (ind < mid) {
int j = update(ind, v[now].l, l, mid);
v[nv].l = j;
} else {
int j = update(ind, v[now].r, mid, r);
v[nv].r = j;
}
v[nv].val = v[v[nv].l].val + v[v[nv].r].val;
return nv;
}
int query(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return 0;
}
if (l >= tl && r <= tr) {
return v[now].val;
}
int mid = (l + r) >> 1;
return
(v[now].l ? query(tl, tr, v[now].l, l, mid) : 0)
+
(v[now].r ? query(tl, tr, v[now].r, mid, r) : 0);
}
};
int n;
std::vector <std::pair <int, int>> a;
std::vector <int> ord, rt;
Seg seg;
void init(int N, int A[], int B[]) {
n = N;
a.resize(n);
for (int i = 0; i < n; i++) {
a[i] = { A[i], B[i] };
}
ord.resize(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [] (int u, int v) -> bool { return a[u] < a[v]; });
rt.resize(n + 1, 0);
for (int i = 1, cnt = 0; i <= n; i++) {
rt[i] = rt[i - 1];
while (cnt < n && i >= a[ord[cnt]].first) {
rt[i] = seg.update(a[ord[cnt]].second, rt[i], 1, n + 1);
cnt++;
}
}
}
int can(int m, int k[]) {
std::sort(k, k + m);
long long sum = 0;
for (int i = 0; i < m; i++) {
sum += k[i];
}
if (sum > n) {
return false;
}
std::vector <std::pair <int, int>> now;
for (int cnt, i = 0; i < m; i++) {
cnt = i;
for (; cnt + 1 < m && k[cnt + 1] == k[cnt]; cnt++);
int num = cnt - i + 1;
now.emplace_back(k[i], k[i] * num);
i = cnt;
}
now.emplace_back(n + 1, 0);
std::vector <int> running(now.size(), 0);
for (int i = 0; i < (int) now.size(); i++) {
int cnt = now[i].second;
for (int j = i; j < (int) now.size() && cnt; j++) {
int x;
int mn = std::min(
x = seg.query(now[j].first, now[j + 1].first, rt[now[i].first], 1, n + 1) - running[j], cnt);
running[j] += mn;
cnt -= mn;
}
if (cnt) {
return false;
}
}
return true;
}
