#include "teams.h"
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
struct node {
int val;
node *lft,*rgt;
node(int _val,node *_l=0,node *_r=0): val(_val),lft(_l),rgt(_r) {}
node* insert(int l,int r,int k) {
if (k<l||k>=r) return this;
if (l+1==r) return new node(this->val+1,lft,rgt);
int m=(l+r)>>1;
return new node(this->val+1,lft->insert(l,m,k),rgt->insert(m,r,k));
}
int query(int l,int r,int ll,int rr) {
if (rr<=l||ll>=r) return 0;
if (ll<=l&&rr>=r) return this->val;
int m=(l+r)>>1;
return lft->query(l,m,ll,rr)+rgt->query(m,r,ll,rr);
}
};
node* root[500100];
int pos[500100];
int n;
void init(int N, int A[], int B[]) {
n=N;
vector<pair<int,int>> student;
for (int i=0;i<N;i++) {
student.push_back({A[i],B[i]});
}
sort(student.begin(),student.end());
root[0]=new node(0);
root[0]->lft=root[0];
root[0]->rgt=root[0];
for (int i=1;i<=n;i++) {
root[i]=root[i-1]->insert(1,N+1,student[i-1].second);
pos[student[i-1].first]=i;
}
for (int i=1;i<=n;i++) {
if (pos[i]==0) pos[i]=pos[i-1];
}
}
int used[5100];
int can(int M, int K[]) {
sort(K,K+M);
vector<int> x;
for (int i=0;i<M;i++) x.push_back(K[i]);
x.resize(unique(x.begin(),x.end())-x.begin());
int nn=x.size();
fill(used,used+nn,0);
int res;
int ptr=0;
int cur;
int ptr2=0;
for (int i=0;i<M;i++) {
while (x[ptr]<K[i]) ptr++;
cur=K[i];
if (i&&K[i]!=K[i-1]) ptr2=ptr;
while (cur&&ptr2<nn) {
res=root[pos[K[i]]]->query(1,n+1,x[ptr2],(ptr2==nn-1)?n+1:x[ptr2+1])-used[ptr2];
used[ptr2]+=min(res,cur);
cur-=min(res,cur);
if (cur==0) break;
ptr2++;
}
if (cur!=0) return 0;
}
return 1;
}
