#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
vector<pii>r;
struct node{
node *lf = NULL,*rg = NULL;
int cnt = 0,l = 0,r = 0;
node(){}
node(int _l,int _r) : l(_l),r(_r){}
node(node *v){
lf = v->lf;
rg = v->rg;
cnt = v->cnt;
l = v->l;
r = v->r;
}
int query(int s,int e){
if(l==s && r==e)return cnt;
int tm = (l+r)/2;
if(s > tm)return rg?rg->query(s,e):0;
else if(e<=tm)return lf?lf->query(s,e):0;
int res = 0;
if(lf)res+=lf->query(s,tm);
if(rg)res+=rg->query(tm+1,e);
return res;
}
};
node*update(node *v,int l,int r,int pos,int x){
if(l==r){
node *res = new node(v);
res->cnt+=x;
return res;
}
int tm = (l+r)/2;
if(!v->rg)v->rg = new node(tm+1,r);
node* res = new node(v);
if(pos<=tm){
if(!v->lf)v->lf = new node(l,tm);
res->lf = update(v->lf,l,tm,pos,x);
}
else {
if(!v->rg)v->rg = new node(tm+1,r);
res->rg = update(v->rg,tm+1,r,pos,x);
}
res->cnt = 0;
if(res->lf)res->cnt+=res->lf->cnt;
if(res->rg)res->cnt+=res->rg->cnt;
return res;
}
vector<node*>root;
void init(int N, int A[], int B[]) {
n = N;
map<int,vector<int>>cnt;
for(int i=0;i<n;i++){
r.push_back({A[i],B[i]});
cnt[A[i]].push_back(B[i]);
}
root.push_back(new node(1,n));
for(int i=1;i<=n;i++){
root.push_back(new node(root.back()));
for(int x:cnt[i])root.back() = update(root.back(),1,n,x,1);
//cout<<root.back()->query(1,n)<<'\n';
}
sort(r.begin(),r.end());
}
int can(int m, int K[]) {
int sum = 0;
map<int,int>cnt;
for(int i=0;i<m;i++){
sum+=K[i];
cnt[K[i]]++;
if(sum>n)return 0;
}
vector<pii>a;
for(auto x:cnt)a.push_back(x);
a.push_back({n+1,0});
int s = a.size();
//for(pii x:a)cout<<x.fi<<" ";
//cout<<'\n';
vector<int>need(s,0);
vector<int>have(s,0);
assert(s<=450);
for(int i=0;i<s;i++)need[i] = a[i].fi * a[i].se;
for(int i=0;i<s;i++){
int l = 0,r = a[i].fi;
if(i)l = a[i-1].fi;
for(int j=i;j+1<s;j++){
int L = a[j].fi;
int R = a[j+1].fi-1;
//cout<<l<<" "<<r<<" "<<L<<" "<<R<<'\n';
//cout<<root[r]->query(L,R)<<'\n';
//cout<<root[l]->query(L,R)<<'\n';
have[j]+=root[r]->query(L,R);
have[j]-=root[l]->query(L,R);
}
for(int j=i;j<s;j++){
if(!need[i])break;
if(have[j]){
int tmp = min(have[j],need[i]);
need[i]-=tmp;
have[j]-=tmp;
}
}
}
//for(int x:need)cout<<x<<" ";
for(int x:need){
if(x)return 0;
}
return 1;
}
