#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(MAXN + 10, make_pair(0, 0)));
for(int i = 1; i <= m; i++){
int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN + 10)) - v - 1;
if(j < 0) return 0;
while(k[i] > pilha.top().first) pilha.pop();
int sum = query(bank[j], 1, n, k[i], k[i]) - query(bank[pilha.top().second.first], 1, n, k[i], k[i]);
int hmin = k[i];
int hmax = k[i];
while(!pilha.empty()){
if(sum >= k[i]) break;
hmax = pilha.top().first;
int diff = query(bank[j], 1, n, hmin + 1, hmax) - query(bank[pilha.top().second.first], 1, n, hmin + 1, hmax);
if(diff + sum >= k[i]){
int ini = hmin + 1, fim = hmax;
while(ini != fim){
int mid = (ini + fim) >> 1;
diff = query(bank[j], 1, n, hmin + 1, mid) - query(bank[pilha.top().second.first], 1, n, hmin + 1, mid);
if(sum + diff >= k[i]) fim = mid;
else ini = mid + 1;
}
hmax = ini;
sum += diff;
break;
}
else sum += diff + pilha.top().second.second, hmin = hmax, pilha.pop();
}
if(sum < k[i]) return 0;
pilha.push(make_pair(hmax, make_pair(j, sum - k[i])));
}
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);
}
