#include "teams.h"
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
pair<int,int>vec[500005];
int n;
vector<int>aint[500005];
bool cmp(pair<int,int>a,pair<int,int>b)
{
if(a.second==b.second)
{
return a.first<b.first;
}
return a.second<b.second;
}
void build(int node,int st,int dr)
{
if(st==dr)
{
aint[node].push_back(vec[st].first);
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
for(int i=st;i<=dr;i++)
{
aint[node].push_back(vec[i].first);
}
sort(aint[node].begin(),aint[node].end());
}
int query(int node,int st,int dr,int qst,int qdr,int val)
{
if(st>qdr || st>dr || qst>dr || qst>qdr)
{
return 0;
}
if(qst<=st && dr<=qdr)
{
return aint[node].size()-(lower_bound(aint[node].begin(),aint[node].end(),val)-aint[node].begin());
}
int mij=(st+dr)/2;
return(query(node*2,st,mij,qst,qdr,val)+query(node*2+1,mij+1,dr,qst,qdr,val));
}
void init(int N, int A[], int B[])
{
n=N;
for(int i=0; i<N; i++)
{
vec[i+1].first=A[i];
vec[i+1].second=B[i];
}
sort(vec+1,vec+n+1,cmp);
build(1,1,n);
}
int dp[1005];
priority_queue<int>pq;
int can(int M, int K[])
{
if(M>=1000)
{
int dr,index=M-1;
sort(K,K+M);
while(pq.size())
{
pq.pop();
}
vec[0].second=-1;
for(int i=n; i>=0; i--)
{
while(vec[i].second<K[index] && index>=0)
{
int cnt=K[index];
while(pq.size() && pq.top()>K[index])
{
pq.pop();
}
while(pq.size() && K[index])
{
K[index]--;
pq.pop();
}
if(K[index]!=0)
{
return 0;
}
else
{
index--;
}
}
pq.push(vec[i].first);
}
return 1;
}
else
{
int dr,index=M-1;
sort(K,K+M);
for(int i=0;i<M;i++)
{
int vec=query(1,1,n,1,K[i],K[i]);
dp[i]=K[i]-vec;
for(int j=0;j<i;j++)
{
dp[i]=max(dp[i],dp[j]+K[i]-query(1,1,n,1,K[j],K[i]));
}
if(dp[i]>=1)
{
return 0;
}
}
return 1;
}
}
