#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
namespace SegmentTree { // Persistent Segment Tree
const int LIM = 2e7;
struct Node {
int value = 0;
int lc = -1;
int rc = -1;
};
vector<Node> d(LIM);
int nodes_cnt = 0;
int Copy(int n) {
d[nodes_cnt] = d[n];
return nodes_cnt++;
}
void Pull(int n, int lc, int rc) {
d[n].value = d[lc].value + d[rc].value;
}
int Update(int n, int tl, int tr, int p, int v) {
if (p < tl || tr < p) return n;
int x = Copy(n);
if (tl == tr) { d[x].value += v; return x; }
int mid = (tl + tr) / 2;
d[x].lc = Update(d[x].lc, tl, mid, p, v);
d[x].rc = Update(d[x].rc, mid + 1, tr, p, v);
Pull(x, d[x].lc, d[x].rc);
return x;
}
int Build(int tl, int tr) {
int n = nodes_cnt++;
if (tl == tr) return n;
int mid = (tl + tr) / 2;
d[n].lc = Build(tl, mid);
d[n].rc = Build(mid + 1, tr);
return n;
}
int Query(int n, int tl, int tr, int p) {
if (tl == tr) return d[n].value;
int mid = (tl + tr) / 2;
if (p <= mid) return Query(d[n].lc, tl, mid, p);
return Query(d[n].rc, mid + 1, tr, p);
}
int SetZero(int n, int tl, int tr, int l, int r) {
if (r < tl || tr < l || tl > tr || l > r) return n;
int x = Copy(n);
if (l <= tl && tr <= r) { d[x].value = 0; return x; }
int mid = (tl + tr) / 2;
d[x].lc = SetZero(d[x].lc, tl, mid, l, r);
d[x].rc = SetZero(d[x].rc, mid + 1, tr, l, r);
Pull(x, d[x].lc, d[x].rc);
return x;
}
}
using namespace SegmentTree;
int N;
int ANSWER;
vector<int> segtree; // segtree[i] = set of active interval's B that contain i
int Walk(int avail, int used, int K, int tl, int tr) { // Use K first Bs of (avail - used)
if (d[avail].value - d[used].value < K) ANSWER = 0;
if (K == 0 || ANSWER == 0) return used;
int x = Copy(used);
if (tl == tr) { d[x].value += K; return x; }
int left_value = d[d[avail].lc].value - d[d[used].lc].value;
int mid = (tl + tr) / 2;
if (K <= left_value) {
d[x].lc = Walk(d[avail].lc, d[x].lc, K, tl, mid);
} else {
d[x].lc = d[avail].lc;
d[x].rc = Walk(d[avail].rc, d[x].rc, K - left_value, mid + 1, tr);
}
Pull(x, d[x].lc, d[x].rc);
return x;
}
void init(int N_, int A[], int B[]) {
N = N_;
segtree.resize(N + 1);
segtree[0] = Build(1, N);
vector<vector<int>> events(N + 2);
for (int i = 0; i < N; i++) {
events[A[i] + 0].emplace_back(i);
events[B[i] + 1].emplace_back(i);
}
vector<int> active(N, 0);
for (int i = 1; i <= N; i++) {
segtree[i] = segtree[i - 1];
map<int, int> add;
for (auto j : events[i]) {
if (active[j]) {
active[j] = 0;
add[B[j]]--;
} else {
active[j] = 1;
add[B[j]]++;
}
}
for (auto j : add) {
segtree[i] = Update(segtree[i], 1, N, j.first, j.second);
}
}
}
int can(int M, int K[]) {
sort(K, K + M); ANSWER = 1;
int old_size = nodes_cnt;
int used = segtree[0];
for (int i = 0; i < M; i++) {
used = SetZero(used, 1, N, 1, K[i] - 1);
used = Walk(segtree[K[i]], used, K[i], 1, N);
}
nodes_cnt = old_size;
return ANSWER;
}
