#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100; // WARNING: SMALL N
int n;
/*class node {
public:
node *l, *r;
int s;
node(int _s) {
s = _s;
l = r = NULL;
}
node(node *lc, node *rc) {
l = lc; r = rc;
s = l -> s + r -> s;
}
};*/
vector<int>value, l, r;
int makenewleaf(int s) {
value.pb(s);
l.pb(-1);
r.pb(-1);
return value.size() - 1;
}
int makenewparent(int lchild, int rchild) {
value.pb(value[lchild] + value[rchild]);
l.pb(lchild);
r.pb(rchild);
return value.size() - 1;
}
vector<int>bs[maxn];
int build(int li=1, int ri=n) {
if(li == ri) return makenewleaf(0);
else {
int mid = (li + ri) / 2;
return makenewparent(build(li, mid), build(mid+1, ri));
}
}
int update(int curr, int x, int li=1, int ri=n) {
if(li == ri) {
return makenewleaf(value[curr]+1);
}
else {
int mid = (li + ri) / 2;
if(x <= mid) return makenewparent(update(l[curr], x, li, mid), r[curr]);
else return makenewparent(l[curr], update(r[curr], x, mid+1, ri));
}
}
// It creates new segment tree such that it takes the first d leafs from f_part
// and the rest of the n - d are from s_part
int removefirst(int d, int f_part, int s_part, int li=1, int ri=n) {
if(li > d) return s_part;
else if(ri <= d) return f_part;
if(li != ri) {
int mid = (li + ri) / 2;
return makenewparent(removefirst(d, l[f_part], l[s_part], li, mid), removefirst(d, r[f_part], r[s_part], mid+1, ri));
}
}
// Takes the first k extra from available that are not in used
int mergeused(int k, int available, int used, int li=1, int ri=n) {
if(li == ri) {
return makenewleaf(value[used] + k);
}
else {
int mid = (li + ri) / 2;
int l_part = value[l[available]] - value[l[used]];
if(l_part >= k)
return makenewparent(mergeused(k, l[available], l[used], li, mid), r[used]);
else
return makenewparent(l[available], mergeused(k - l_part, r[available], r[used], mid+1, ri));
}
}
int emp;
int persistent_tree[maxn];
void init(int N, int A[], int B[]) {
n = N;
for(int i=0;i<n;i++) {
bs[A[i]].pb(B[i]);
}
emp = build();
persistent_tree[0] = emp;
for(int i=1;i<=n;i++) {
persistent_tree[i] = persistent_tree[i-1];
persistent_tree[i] = removefirst(i-1, emp, persistent_tree[i]); // We don't care for the interavals starting before my position
for(int j:bs[i]) {
persistent_tree[i] = update(persistent_tree[i], j);
}
}
}
int can(int M, int K[]) {
sort(K, K+M);
int used = emp;
for(int i=0;i<M;i++) {
used = removefirst(K[i]-1, emp, used);
if(value[persistent_tree[K[i]]] - value[used] < K[i]) return 0;
used = mergeused(K[i], persistent_tree[K[i]], used);
}
return 1;
}
