#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 5e3 + 3;
struct BIT {
int b[nax] = {0};
int query(int p) {
assert(p>0);
int ret = 0;
while(p>0) {
ret += b[p];
p -= p&-p;
}
return ret;
}
int query(int l, int r) {
int ret = query(r);
if(l>1) ret -= query(l-1);
return ret;
}
void update(int p, int val) {
assert(p>0);
while(p<nax) {
b[p] += val;
p += p&-p;
}
}
} both, one;
vector<int>mst[nax * 4];
int n;
vector<int>atob[nax];
void build(int l, int r, int v) {
if(l==r) {
mst[v] = atob[l];
return;
}
int mid = (l+r)/2;
build(l, mid, v*2);
build(mid+1, r, v*2+1);
mst[v].resize(mst[v*2].size() + mst[v*2+1].size());
merge(mst[v*2].begin(), mst[v*2].end(), mst[v*2+1].begin(), mst[v*2+1].end(),
mst[v].begin());
}
int query(int l, int r, int L, int R, int v) {
if(l>=L && r<=R) {
int ret = upper_bound(mst[v].begin(), mst[v].end(), R) -
mst[v].begin();
return ret;
}
if(l>R || r<L) return 0;
int mid = (l+r)/2;
return query(l, mid, L, R, v*2) + query(mid+1, r, L, R, v*2+1);
}
void init(int N, int A[], int B[]) {
n = N;
for(int i=0; i<N; ++i) {
both.update(A[i], 1);
both.update(B[i]+1, -1);
one.update(B[i], 1);
}
for(int i=0; i<n; ++i) {
atob[A[i]].push_back(B[i]);
}
for(int i=1; i<=n; ++i) {
sort(atob[i].begin(), atob[i].end());
}
build(1, n, 1);
}
int can(int M, int K[]) {
sort(K, K+M);
int need[M];
for(int i=0; i<M; ++i) {
need[i] = K[i];
}
for(int i=0; i<M; ++i) {
if(both.query(K[i])<need[i]) return 0;
if(i==M-1) break;
if(K[i]==K[i+1]) {
need[i+1] += need[i];
continue;
}
int ends_in_between = one.query(K[i], K[i+1]-1);
if(K[i]+1<K[i+1]) {
ends_in_between -= query(1, n, K[i]+1, K[i+1]-1, 1);
}
if(need[i]>ends_in_between) {
need[i+1] += need[i] - ends_in_between;
}
}
return 1;
}
