#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,lg=19,kaf=(1<<19),maxq=maxn;
vector<pair<int,int>>alle;
int n,dproot[maxn],root,m;
vector<int>ezaf[maxn];
vector<int>all;
vector<pair<int,int>>unnow;
struct segment{
struct node{
int cl,cr,w;
node(){
w=0;
cl=cr=0;
}
};
node seg[maxq*lg*4];
int te=1;
int upd(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl||tl>tr){
return i;
}
int u=te;
seg[te]=seg[i];
te++;
if(l>=tl&&r<=tr){
seg[u].w+=w;
return u;
}
int mid=(l+r)>>1;
seg[u].cl=upd(seg[u].cl,l,mid,tl,tr,w);
seg[u].cr=upd(seg[u].cr,mid+1,r,tl,tr,w);
seg[u].w=seg[seg[u].cl].w+seg[seg[u].cr].w;
return u;
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i].w;
}
int mid=(l+r)>>1;
return pors(seg[i].cl,l,mid,tl,tr)+pors(seg[i].cr,mid+1,r,tl,tr);
}
}seg;
void init(int N, int A[], int B[]) {
n=N;
for(int i=0;i<n;i++){
alle.push_back(make_pair(A[i],B[i]));
ezaf[alle[i].second].push_back(alle[i].first);
}
for(int i=1;i<=n;i++){
for(auto x:ezaf[i]){
root=seg.upd(root,0,kaf-1,x,x,1);
}
dproot[i]=root;
}
}
int upd(int w,int ind,int mn=0){
if((int)unnow.size()==0){
return 0;
}
int z=seg.pors(dproot[unnow.back().second],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
//cout<<w<<" "<<ind<<" "<<mn<<" "<<z<<" "<<unnow.back().first<<" "<<unnow.back().second<<endl;
if(z<w){
w-=z;
int f=unnow.back().first;
unnow.pop_back();
return upd(w,ind,f);
}
int low=mn,high=unnow.back().second+1,mid;
while(high-low>1){
mid=(high+low)>>1;
z=seg.pors(dproot[mid],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
if(z>w){
high=mid;
}else{
low=mid;
}
}
unnow.push_back(make_pair(ind+1,low));
return 1;
}
int can(int M, int K[]) {
m=M;
for(int i=0;i<m;i++){
all.push_back(K[i]);
}
sort(all.begin(),all.end());
unnow.clear();
unnow.push_back(make_pair(1,n));
for(int i=0;i<m;i++){
if(upd(all[i],all[i])==0){
return 0;
}
}
return 1;
}
