#include "teams.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n;
vector<int> sweep[500005];
int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;
void upd(int bf, int &nd, int cl, int cr, int v){
nd = ++ sz;
lf[nd] = lf[bf]; rg[nd] = rg[bf]; sum[nd] = sum[bf] + 1;
if(cl == cr) return;
if(v <= (cl + cr) / 2)
upd(lf[bf], lf[nd], cl, (cl + cr) / 2, v);
else
upd(rg[bf], rg[nd], (cl + cr) / 2 + 1, cr, v);
}
int que(int nd, int cl, int cr, int ql, int qr){
if(qr < cl || cr < ql || cl > cr) return 0;
if(ql <= cl && cr <= qr) return sum[nd];
return que(lf[nd], cl, (cl + cr) / 2, ql, qr) + que(rg[nd], (cl + cr) / 2 + 1, cr, ql, qr);
}
void init(int N, int A[], int B[]){
n = N;
for(int i = 0; i < n; i ++)
sweep[A[i]].push_back(B[i]);
for(int i = 1; i <= n; i ++){
rt[i] = rt[i - 1];
for(int x : sweep[i])
upd(rt[i], rt[i], 1, n, x);
}
}
int val[500005], cnt[500005], used[500005];
int block = 707; // sqrt(N)
int can(int M, int K[]){
if(M > block){
// (N + M) log N -> sqrt(N) * (N + sqrt(N)) log N = N * sqrt(N) * log N
vector<int> cnt(n + 1, 0);
for(int i = 0; i < M; i ++)
cnt[K[i]] += K[i];
priority_queue<int, vector<int>, greater<int> > pq;
for(int i = 1; i <= n; i ++){
for(int x : sweep[i]) pq.push(x);
while(pq.size() && pq.top() < i) pq.pop();
if(pq.size() < cnt[i]) return 0;
for(; cnt[i] --; pq.pop());
}
return 1;
}
else{
// M^2 log N -> sqrt(N) * (sqrt(N)) ^ 2 log N = N sqrt(N) log(N)
sort(K, K + M);
int sum = 0, id = 0;
for(int i = 0; i < M; i ++){
sum += K[i];
if(id > 0 && val[id - 1] == K[i])
cnt[id - 1] += K[i];
else
val[id] = cnt[id] = K[i], id ++;
}
val[id] = n + 1;
if(sum > n) return 0;
for(int i = 0; i < id; i ++)
used[i] = 0;
for(int i = 0; i < id; i ++){
int need = cnt[i];
for(int j = i; j < id; j ++){
int have = que(rt[val[i]], 1, n, val[j], val[j + 1] - 1) - used[j];
int add = min(have, need);
need -= add; used[j] += add;
if(need <= 0) break;
}
if(need > 0) return 0;
}
return 1;
}
return 69;
}
