#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
int n;
pair<int, int> v[MAXN];
int bank[MAXN];
int m;
int k[MAXN];
vector<int> seg, e, d;
int create();
int copia(int pos);
int update(int pos, int ini, int fim, int id);
int query(int pos, int ini, int fim, int p, int q);
void init(int N, int A[], int B[]) {
n = N;
create();
bank[0] = create();
for(int i = 0; i < n; i++)
v[i + 1] = make_pair(A[i], B[i]);
sort(v + 1, v + 1 + n);
for(int i = 1; i <= n; i++)
bank[i] = update(bank[i - 1], 1, n, v[i].second);
}
int can(int M, int K[]) {
m = M;
for(int i = 0; i < m; i++)
k[i + 1] = K[i];
sort(k + 1, k + 1 + m);
stack<pair<int, pair<int, int> > > pilha;
pilha.push(make_pair(n + 1, make_pair(0, 0)));
for(int i = 1; i <= m; i++){
int it = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
if(it < 0) return 0;
int hmin = k[i];
int hmax = k[i];
int sum = 0;
while(pilha.top().first < hmin) pilha.pop();
sum += query(bank[it], 1, n, hmin, hmin) - query(bank[pilha.top().second.second], 1, n, hmin, hmin);
while(!pilha.empty()){
hmax = pilha.top().first;
int it2 = pilha.top().second.first;
sum += pilha.top().second.second;
int diff = query(bank[it], 1, n, hmin + 1, hmax) - query(bank[it2], 1, n, hmin + 1, hmax);
if(diff + sum >= k[i]){
int ini = hmin, fim = hmax;
while(ini != ini){
int mid = (ini + fim) >> 1;
int diff = query(bank[it], 1, n, hmin + 1, mid) - query(bank[it2], 1, n, hmin + 1, mid);
if(ini == fim - 1) mid = fim;
if(sum + diff >= k[i]) ini = mid;
else fim = mid - 1;
}
pilha.push(make_pair(ini, make_pair(it, sum - k[i])));
break;
}
else sum += diff, hmin = hmax, pilha.pop();
}
if(pilha.empty()) return 0;
}
return 1;
}
int create(){
seg.push_back(0);
e.push_back(0);
d.push_back(0);
return seg.size() - 1;
}
int copia(int pos){
seg.push_back(seg[pos]);
e.push_back(e[pos]);
d.push_back(d[pos]);
return seg.size() - 1;
}
int update(int pos, int ini, int fim, int id){
if(ini > id || fim < id) return pos;
int newNode = copia(pos);
if(ini == fim){
seg[newNode]++;
return newNode;
}
int mid = (ini + fim) >> 1;
int aux = update(e[pos], ini, mid, id);
e[newNode] = aux;
aux = update(d[pos], mid + 1, fim, id);
d[newNode] = aux;
seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
return newNode;
}
int query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return 0;
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1;
return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q);
}
