#include "teams.h"
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <assert.h>
#define ll long long
using namespace std;
int N;
pair<int,int> ivs [500000];
int cNod = 5;
//roots[i] = all the rs after l
int roots [500000];
int val [5000000];
int lc [5000000];
int rc [5000000];
int nnod(){
cNod++;
return cNod;
}
int build(int cur, int l, int r){
if(l == r){
return cur;
}else{
lc[cur] = nnod();
rc[cur] = nnod();
build(lc[cur], l, (l+r)/2);
build(rc[cur], (l+r)/2+1, r);
return cur;
}
}
int change(int cur, int l, int r, int x){
if(l <= x && x <= r){
int ncur = nnod();
val[ncur] = val[cur]+1;
if(l != r){
lc[ncur] = change(lc[cur], l, (l+r)/2, x);
rc[ncur] = change(rc[cur], (l+r)/2+1, r, x);
}
return ncur;
}else{
return cur;
}
}
int query(int cur, int l, int r, int fl, int fr){
if(fl > fr){
return 0;
}
if(fl <= l && r <= fr){
return val[cur];
}else if(fr < l || r < fl){
return 0;
}else{
return query(lc[cur], l, (l+r)/2, fl, fr) + query(rc[cur], (l+r)/2+1, r, fl, fr);
}
}
void init(int N_, int A_[], int B_[]) {
N = N_;
for(int i = 0; i < N; i++){
ivs[i] = make_pair(A_[i], B_[i]);
}
sort(ivs, ivs+N);
roots[0] = build(nnod(), 1, N);
int c = 0;
for(int i = 1; i <= N; i++){
int croot = roots[i-1];
while(c != N && i == ivs[c].first){
// cout << "!" << i << " " << ivs[c].first << " " << ivs[c].second << endl;
croot = change(croot, 1, N, ivs[c].second);
c++;
}
roots[i] = croot;
}
cerr << "INIT DONE!" << endl;
}
int can(int M, int K[]) {
sort(K, K+M);
int su = 0;
for(int i = 0; i < M; i++){
su += K[i];
}
if(su > N){
return 0;
}else{
if(M <= 500){
// cerr << "PROCESSING" << endl;
//M^2 log
int cnt [M][M];
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
cnt[i][j] = 0;
}
}
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
if(j == M-1){
cnt[i][j] = query(roots[K[i]], 1, N, K[j], N);
}else{
cnt[i][j] = query(roots[K[i]], 1, N, K[j], K[j+1]-1);
}
}
}
// cerr << "CNT INIT" << endl;
for(int i = M-1; i >= 1; i--){
for(int j = i; j < M; j++){
cnt[i][j] = cnt[i][j] - cnt[i-1][j];
}
}
int cnt2 [M][M];
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
cnt2[i][j] = 0;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
for(int k = j; k < M; k++){
int lb1 = 1;
int rb1 = K[j];
if(j != 0){
lb1 = K[j-1] + 1;
}
int lb2 = K[k];
int rb2 = N;
if(k != M-1){
rb2 = K[k+1] - 1;
}
// cout << lb1 << " " << rb1 << " " << lb2 << " " << rb2 << endl;
if(lb1 <= ivs[i].first && ivs[i].first <= rb1 && lb2 <= ivs[i].second && ivs[i].second <= rb2){
cnt2[j][k]++;
}
}
}
}
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
cerr << cnt[i][j] << " ";
}
cerr << endl;
}
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
cerr << cnt2[i][j] << " ";
}
cerr << endl;
}
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
assert(cnt2[i][j] == cnt[i][j]);
}
}
/* for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
cerr << cnt[i][j] << " ";
}
cerr << endl;
}
cerr << endl;*/
//left endpoint, right endpoint
priority_queue <pair<int,int>, vector<pair<int,int>>, greater <pair<int,int>>> pq;
for(int i = 0; i < M; i++){
for(int j = i; j < M; j++){
if(cnt[i][j] > 0){
pq.push(make_pair(j, i));
}
}
int c = K[i];
while(!pq.empty()){
int r = pq.top().first;
int l = pq.top().second;
if(cnt[l][r] <= c){
c -= cnt[l][r];
cnt[l][r] = 0;
pq.pop();
}else{
cnt[l][r] -= c;
c = 0;
break;
}
}
if(c > 0){
return 0;
}
}
}else{
//N+M log
//do a manual scan
priority_queue <int, vector<int>, greater <int>> pq;
int cptr = 0;
for(int i = 0; i < M; i++){
while(cptr < N && ivs[cptr].first <= K[i]){
pq.push(ivs[cptr].second);
cptr++;
}
//remove not useful students
while(!pq.empty() && (pq.top()) < K[i]){
pq.pop();
}
if((int)(pq.size()) < K[i]){
return 0;
}else{
for(int j = 0; j < K[i]; j++){
pq.pop();
}
}
}
}
return 1;
}
}
