#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>bs[maxn];
node *zero;
node *build(int li=1, int ri=n) {
if(li == ri) return zero;
else {
int mid = (li + ri) / 2;
return new node(build(li, mid), build(mid+1, ri));
}
}
node *update(node *curr, int x, int li=1, int ri=n) {
if(li == ri) {
curr->s = curr->s + 1;
return curr;
}
else {
int mid = (li + ri) / 2;
if(x <= mid) return new node(update(curr->l, x, li, mid), curr->r);
else return new node(curr->l, update(curr->r, 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
node *removefirst(int d, node *f_part, node *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 new node(removefirst(d, f_part->l, s_part->l, li, mid), removefirst(d, f_part->r, s_part->r, mid+1, ri));
}
}
// Takes the first k extra from available that are not in used
node *mergeused(int k, node *available, node *used, int li=1, int ri=n) {
if(li == ri) {
used->s = used->s + k;
return used;
}
else {
int mid = (li + ri) / 2;
int l_part = available->l->s - used->l->s;
if(l_part >= k)
return new node(mergeused(k, available->l, used->l, li, mid), used->r);
else
return new node(available->l, mergeused(k - l_part, available->r, used->r, mid+1, ri));
}
}
node *emp;
node *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]);
}
zero = new node(0);
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);
node *used = emp;
for(int i=0;i<M;i++) {
used = removefirst(K[i]-1, emp, used);
if(persistent_tree[K[i]]->s - used->s < K[i]) return 0;
used = mergeused(K[i], persistent_tree[K[i]], used);
}
return 1;
}
