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