#include<bits/stdc++.h>
#include "teams.h"
#define fi first
#define se second
using namespace std;
const int NN=5e5;
int pot;
struct Tree
{
Tree *son[2];
int l,r;
vector<int> t;
Tree(int _l,int _r) : l(_l),r(_r)
{
son[0]=son[1]=NULL;
}
~Tree()
{
delete son[0];
delete son[1];
}
void sort_subtree()
{
sort(t.begin(),t.end());
for(int i:{0,1})
{
if(son[i]!=NULL)
son[i]->sort_subtree();
}
return;
}
Tree* go(bool dir)
{
if(son[dir]==NULL)
{
if(!dir)
son[dir]=new Tree(l,(l+r)/2);
else
son[dir]=new Tree((l+r)/2+1,r);
}
return son[dir];
}
void add(int x,int y)
{
t.push_back(y);
if(l==r)
return;
int mid=(l+r)/2;
if(x<=mid)
go(0)->add(x,y);
else
go(1)->add(x,y);
return;
}
int cnt(int x)
{
if(t[0]>x)
return 0;
int bg=0,en=t.size()-1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(t[mid]<=x)
bg=mid;
else
en=mid-1;
}
return bg+1;
}
int read_son(int lx,int rx,int ly,int ry,bool dir)
{
if(son[dir]!=NULL)
return son[dir]->read(lx,rx,ly,ry);
return 0;
}
int read(int lx,int rx,int ly,int ry)
{
if(lx<=l && r<=rx)
return cnt(ry)-cnt(ly-1);
int mid=(l+r)/2;
int ans=0;
if(lx<=mid)
ans+=read_son(lx,rx,ly,ry,0);
if(mid+1<=rx)
ans+=read_son(lx,rx,ly,ry,1);
return ans;
}
};
int n;
Tree *root;
int t[NN+10];
int dp[NN+10];
vector<int> st;
int get_val(int j,int k)
{
return dp[j]-(root->read(k,pot,1,t[j]));
}
int when_better(int a,int b)
{
#warning log^3
// TEMPORARY
int bg=1,en=pot;
while(bg<en)
{
int mid=(bg+en)/2;
if(get_val(a,mid)<=get_val(b,mid))
en=mid;
else
bg=mid+1;
}
if(get_val(a,bg)>get_val(b,bg))
return pot+1;
return bg;
}
void init(int N,int A[],int B[])
{
n=N;
for(pot=1;pot<n;pot*=2);
root=new Tree(1,pot);
for(int i=0;i<n;i++)
root->add(B[i],A[i]);
root->sort_subtree();
return;
}
int can(int M,int K[])
{
long long sum=0;
sort(K,K+M);
for(int i=0;i<M;i++)
{
t[i+1]=K[i];
sum+=K[i];
}
if(sum>n)
return 0;
st.clear();
st.push_back(0);
for(int i=1;i<=M;i++)
{
while(st.size()>1 && get_val(st[st.size()-2],t[i])<=get_val(st.back(),t[i]))
st.pop_back();
dp[i]=get_val(st.back(),t[i])+(root->read(t[i],pot,1,t[i]))-t[i];
//cerr<<"dp["<<i<<"]="<<dp[i]<<"\n";
if(dp[i]<0)
return 0;
while(st.size()>1 && when_better(st[st.size()-2],st.back())<=when_better(st.back(),i))
st.pop_back();
if(get_val(st.back(),t[i])>get_val(i,t[i]))
st.push_back(i);
}
return 1;
}
