#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int deb, fin, val, l = -1, r = -1;
};
const int N = 1 << 19;
vector<Node> node;
vector<int> posFin[N];
pair<int, int> inter[N];
int n, root[N], nbFin[N], nbDeb[N];
int nodeCopy(int id) {
int i = node.size();
node.push_back(node[id]);
return i;
}
int newNode(int deb, int fin) {
int i = node.size();
node.push_back({deb, fin, 0});
return i;
}
int add(int i, int pos) {
if(pos < node[i].deb || node[i].fin <= pos)
return i;
i = nodeCopy(i);
node[i].val++;
if(node[i].fin - node[i].deb == 1)
return i;
int mid = (node[i].deb + node[i].fin) / 2;
if(node[i].l == -1) {
int x = newNode(node[i].deb, mid);
node[i].l = x;
}
if(node[i].r == -1) {
int x = newNode(mid, node[i].fin);
node[i].r = x;
}
int left = add(node[i].l, pos),
right = add(node[i].r, pos);
node[i].l = left, node[i].r = right;
return i;
}
int getSum(int i, int deb, int fin) {
if(i == -1)
return 0;
if(deb <= node[i].deb && node[i].fin <= fin)
return node[i].val;
if(fin <= node[i].deb || node[i].fin <= deb)
return 0;
return getSum(node[i].l, deb, fin) + getSum(node[i].r, deb, fin);
}
int getId(int i, int search) {
if(node[i].fin - node[i].deb == 1)
return node[i].deb;
if(node[i].l == -1)
return getId(node[i].r, search);
if(search <= node[node[i].l].val)
return getId(node[i].l, search);
return getId(node[i].r, search - node[node[i].l].val);
}
void init(int X, int A[], int B[]) {
n = X;
for(int i = 0; i < n; i++)
inter[i] = {A[i], B[i]};
sort(inter, inter + n);
/*
n = X;
for(int i = 0; i < n; i++) {
B[i]++;
nbDeb[A[i]]++;
nbFin[B[i]]++;
posFin[A[i]].push_back(B[i]);
}
for(int i = 1; i < N; i++) {
nbDeb[i] += nbDeb[i-1];
nbFin[i] += nbFin[i-1];
}
root[0] = 0;
node.push_back({0, N, 0});
for(int i = 1; i <= n; i++) {
root[i] = root[i-1];
for(int j : posFin[i])
root[i] = add(root[i], j);
}*/
}
int can(int m, int k[]) {
sort(k, k + m);
int id = 0;
multiset<int> fin;
for(int i = 0; i < m; i++) {
while(id < n && inter[id].first <= k[i]) {
fin.insert(inter[id].second);
id++;
}
int nb = k[i];
while(!fin.empty() && nb) {
auto it = fin.begin();
if((*it) >= k[i])
nb--;
fin.erase(it);
}
if(nb > 0)
return 0;
}
return 1;
/*
sort(k, k + m);
int preK = 0, last = 0, nbPre = 0;
for(int i = 0; i < m; i++) {
//trouver cb d'intervalles qu'on aurait pu prendre ont ete pris
int taken = getSum(root[preK], k[i]+1, last);
if(last >= k[i]+1)
taken += nbPre;
//l'id du dernier pris (1-indexed)
int id = nbFin[k[i]] + taken + k[i];
if(id > nbDeb[k[i]])
return 0;
//trouver le dernier pris
last = getId(root[k[i]], id);
nbPre = id - getSum(root[k[i]], 0, last);
preK = k[i];
}
return 1;*/
}
