#include "teams.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second
struct Vertex{
int sum;
Vertex *l, *r;
Vertex(int Sum=0) : sum(Sum), l(NULL), r(NULL){}
Vertex(Vertex* le, Vertex* ri) : sum(le->sum + ri->sum), l(le), r(ri){}
};
Vertex* build(int tl, int tr){
if(tl==tr) return new Vertex;
int tm = (tl+tr)>>1;
return new Vertex(build(tl, tm), build(tm+1, tr));
}
int sum(Vertex* v, int tl, int tr, int l, int r){
if(l>r) return 0;
if(l==tl && r==tr) return v->sum;
int tm = (tl+tr)>>1;
return sum(v->l, tl, tm, l, min(r, tm)) + sum(v->r, tm+1, tr, max(l, tm+1), r);
}
Vertex* modify(Vertex* v, int tl, int tr, int p, int value){
int tm = (tl+tr)>>1;
if(tl==tr) return new Vertex(v->sum+value);
if(p<=tm) return new Vertex(modify(v->l, tl, tm, p, value), v->r);
else return new Vertex(v->l, modify(v->r, tm+1, tr, p, value));
}
const int MAXN=500010, SQ=1010;
int n, aa[MAXN], bb[MAXN], uniq[SQ], req[SQ], arr[SQ][SQ];
pii stu[MAXN];
Vertex* roots[MAXN];
void init(int N, int A[], int B[]) {
n=N;
forn(i, n) stu[i].F=aa[i]=A[i], stu[i].S=bb[i]=B[i];
sort(stu, stu+n);
sort(aa, aa+n);
sort(bb, bb+n);
roots[0]=build(0, n-1);
forn(i, n){
int posB=lower_bound(bb, bb+n, stu[i].S)-bb;
roots[i+1]=modify(roots[i], 0, n-1, posB, 1);
}
}
int count(int tx, int ty){
int x = upper_bound(aa, aa+n, tx) - aa;
int y = upper_bound(bb, bb+n, ty) - bb;
if(y==0) return 0;
return sum(roots[x], 0, n-1, 0, y-1);
}
int count(int tx1, int tx2, int ty1, int ty2){
return count(tx1, ty1) + count(tx2, ty2) - count(tx1, ty2) - count(tx2, ty1);
}
int can(int m, int K[]) {
int suu=0, sz=0;
forn(i, m){
suu+=K[i];
if(suu>n) return 0;
}
sort(K, K+m);
forn(i, m){
if(i==0 || K[i]!=K[i-1]) uniq[sz]=K[i], req[sz]=1, ++sz;
else req[sz-1]++;
}
forn(i, sz) req[i]*=uniq[i];
forn(i, sz) forsn(j, i, sz) arr[i][j]=0;
forn(i, sz) forsn(j, i, sz){
int tx1 = (i? uniq[i-1] : 0), tx2=uniq[i];
int ty1 = uniq[j]-1, ty2 = (j==sz-1? MAXN : uniq[j+1]-1);
arr[i][j]=count(tx1, tx2, ty1, ty2);
}
forn(i, sz){
forsn(j, i, sz){
if(req[i]>arr[i][j]) req[i]-=arr[i][j], arr[i][j]=0;
else{
arr[i][j]-=req[i];
req[i]=0;
break;
}
}
if(req[i]>0) return 0;
forsn(j, i+1, sz) arr[i+1][j]+=arr[i][j];
}
return 1;
}
