#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
const int MAXN = 2e6 + 10;
const int LOG = 22;
int nodeInd , tot , seg[MAXN * LOG] , lc[MAXN * LOG] , rc[MAXN * LOG] , root[MAXN];
vector<int> vec[MAXN];
void build(int id , int l = 0 , int r = MAXN){
if(r - l == 1) return;
lc[id] = ++nodeInd;
rc[id] = ++nodeInd;
int mid = l + r >> 1;
build(lc[id] , l , mid);
build(rc[id] , mid , r);
}
int add(int x , int cid , int l = 0 , int r = MAXN){
int id = ++nodeInd;
seg[id] = seg[cid]; lc[id] = lc[cid]; rc[id] = rc[cid];
if(r - l == 1){
seg[id]++;
return id;
}
int mid = l + r >> 1;
if(x < mid) lc[id] = add(x , lc[id] , l , mid);
else rc[id] = add(x , rc[id] , mid , r);
seg[id] = seg[lc[id]] + seg[rc[id]];
return id;
}
int get(int ql , int qr , int id , int l = 0 , int r = MAXN){
if(qr <= l || r <= ql) return 0;
if(ql <= l && r <= qr) return seg[id];
int mid = l + r >> 1;
return get(ql , qr , lc[id] , l , mid) + get(ql , qr , rc[id] , mid , r);
}
int solve(int x , int val , int cid , int id2 , int l = 0 , int r = MAXN){
if(r <= x || val == tot) return cid;
int id1 = ++nodeInd;
seg[id1] = seg[cid]; lc[id1] = lc[cid]; rc[id1] = rc[cid];
if(x <= l && (seg[id2] - seg[id1] + tot <= val || r - l == 1)){
int cnt = min(val - tot , seg[id2] - seg[id1]); tot += cnt;
// cout << x << ' ' << val << ' ' << cnt << ' ' << seg[id1] << ' ' << seg[id2] << ' ' << l << ' ' << r << endl;
seg[id1] += cnt; lc[id1] = lc[id2]; rc[id1] = rc[id2];
return id1;
}
int mid = l + r >> 1;
lc[id1] = solve(x , val , lc[id1] , lc[id2] , l , mid);
rc[id1] = solve(x , val , rc[id1] , rc[id2] , mid , r);
seg[id1] = seg[lc[id1]] + seg[rc[id1]];
return id1;
}
void init(int N, int A[], int B[]) {
for(int i = 0 ; i < N ; i++) vec[A[i]].push_back(B[i]);
build(0);
for(int i = 1 ; i <= N ; i++){
root[i] = root[i - 1];
for(int j : vec[i]){
root[i] = add(j , root[i]);
}
}
}
int can(int M, int K[]) {
int cur = 0;
sort(K , K + M);
for(int i = 0 ; i < M ; i++){
tot = 0 , cur = solve(K[i] , K[i] , cur , root[K[i]]);
// cout << tot << endl;
if(tot < K[i]) return 0;
}
return 1;
}
