#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
// #define esq(x) x << 1
// #define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e5 + 10;
vector<int> seg, esq, dir;
int roots[MAXN];
pii ints[MAXN];
int tot;
int create(){
seg.pb(0);
esq.pb(0);
dir.pb(0);
return seg.size() - 1;
}
int copy(int node){
seg.pb(seg[node]);
esq.pb(esq[node]);
dir.pb(dir[node]);
return seg.size() - 1;
}
int update(int node, int x, int y, int id, int val){
if(x > id || y < id) return node;
int nn = copy(node);
if(x == y){
seg[nn] = seg[node] + val;
return nn;
}
int aux = update(esq[node], x, mid(x,y,0), id, val);
esq[nn] = aux;
aux = update(dir[node], mid(x,y,1), y, id, val);
dir[nn] = aux;
seg[nn] = seg[dir[nn]] + seg[esq[nn]];
//("%d %d \n", nn, seg[nn]);
return nn;
}
int copyint(int node1, int node2, int x, int y, int l, int r){
if(x > r || y < l) return node1;
int nn = copy(node2);
if(x >= l && y <= r) return node2;
int aux = copyint(esq[node1], esq[node2], x, mid(x,y,0), l, r);
esq[nn] = aux;
aux = copyint(dir[node1], dir[node2], mid(x,y,1), y, l, r );
dir[nn] = aux;
seg[nn] = seg[esq[nn]] + seg[dir[nn]];
return nn;
}
pii bb(int node1, int node2, int x, int y, int l, int r, int val){
//("%d %d %d %d\n", l, r, x, y);
if(x > r|| y < l) return {y+1,0};
if(x >= l && y <= r && seg[node1]-seg[node2] < val) return{y+1, seg[node1] - seg[node2]};
if(x == y) return {x,0};
pii aux = bb(esq[node1], esq[node2], x, mid(x,y,0), l, r, val);
if(aux.fi <= mid(x,y,0)) return aux;
pii aux2 = bb(dir[node1], dir[node2], mid(x,y,1), y, l, r, val-aux.second);
return {aux2.first, aux2.second + aux.second};
}
int n;
void init(int N, int A[], int B[]) {
n = N;
vector<pii> v;
for(int i = 0; i < n; i++)v.pb({A[i], B[i]});
sort(v.begin(), v.end());
create();
//("%d\n", roots[0]);
for(int i = 0; i < n; i++) ints[i+1] = v[i];
int it2 = 1;
for(int i = 1; i <= n; i++){
roots[i] = roots[i-1];
while(ints[it2].fi == i){
int aux = update(roots[i], 1, n, ints[it2++].se, 1);
roots[i] = aux;
}
}
}
int can(int m, int K[]) {
sort(K, K + m);
//("B\n");
int last = 0;
for(int i = 0; i < m; i++){
int r = K[i];
pii aux = bb(roots[r], last, 1, n, r, n, r);
//("A %d %d\n", r - aux.se, aux.fi);
if(aux.fi == n + 1) return 0;
//("%d\n", i);
last = copyint(last, roots[r], 1, n, 1, aux.fi-1);
last = update(last, 1, n , aux.fi, r - aux.se);
}
return 1;
}
