#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
// ------------------------ Segtree Library ----------------------
int size_ = 1;
vector<int> dat[1 << 21];
void initialize(int sz) {
size_ = 1; for (int i = 0; i < 128; i++) dat[i].clear();
while (size_ <= sz) size_ *= 2;
}
void add(int px, int py) {
py += size_; dat[py].push_back(px);
while (py >= 2) {
py >>= 1;
dat[py].push_back(px);
}
}
void syncronization() {
for (int i = 1; i < size_ * 2; i++) sort(dat[i].begin(), dat[i].end());
}
int counts(int u, int lx, int rx) {
// 閉区間
int pos1 = lower_bound(dat[u].begin(), dat[u].end(), lx) - dat[u].begin();
int pos2 = lower_bound(dat[u].begin(), dat[u].end(), rx + 1) - dat[u].begin();
return (pos2 - pos1);
}
int query_(int lx, int rx, int ly, int ry, int a, int b, int u) {
if (ly <= a && b <= ry) return counts(u, lx, rx);
if (b <= ly || ry <= a) return 0;
int s1 = query_(lx, rx, ly, ry, a, (a + b) >> 1, u * 2);
int s2 = query_(lx, rx, ly, ry, (a + b) >> 1, b, u * 2 + 1);
return s1 + s2;
}
int query(int lx, int rx, int ly, int ry) {
// 閉区間
return query_(lx, rx, ly, ry + 1, 0, size_, 1);
}
int getmin(int lef_x, int lim_x, int num) {
int u = 2; num--;
while (u < size_ * 2) {
int G = counts(u, lef_x, lim_x);
if (G <= num) { num -= G; u++; u *= 2; }
else { u *= 2; }
}
if (u == (size_ << 2) - 2) return (1 << 30);
return (u >> 1) - size_;
}
// ------------------------ Segree Library -----------------------
int cnte[1 << 20], mid[1 << 20], cntt[1 << 20];
void init(int N, int A[], int B[]) {
for (int i = 0; i <= 128; i++) { cnte[i] = 0; mid[i] = 0; cntt[i] = 0; }
for (int i = 0; i < N; i++) { cnte[A[i]]++; cnte[B[i]]++; }
for (int i = 1; i <= N; i++) cnte[i] += cnte[i - 1];
for (int i = 0; i < N; i++) { A[i] = cnte[A[i] - 1] + cntt[A[i]]; cntt[A[i]]++; }
for (int i = 1; i <= N; i++) mid[i] = cnte[i - 1] + A[i];
for (int i = 0; i < N; i++) { B[i] = cnte[B[i] - 1] + cntt[B[i]]; cntt[B[i]]++; }
initialize(N * 2 + 1);
for (int i = 0; i < N; i++) add(A[i], B[i]);
syncronization();
}
int can(int M, int K[]) {
sort(K, K + M);
vector<tuple<int, int, int>> V; V.push_back(make_tuple(0, (1 << 30), 0));
for (int i = 0; i < M; i++) {
int life = K[i], cx = mid[K[i]];
while (V.size() >= 1) {
tuple<int, int, int> F = V[V.size() - 1];
if (get<1>(F) < mid[K[i]]) { V.pop_back(); continue; }
int E = query(get<0>(F) + 1, mid[K[i]], cx, get<1>(F));
if (life > E) { life -= E; cx = get<1>(F) + 1; V.pop_back(); }
else {
int S = life + query(get<0>(F) + 1, mid[K[i]] - 1, get<0>(F) + 1, mid[K[i]] - 1);
int cx = getmin(get<0>(F) + 1, mid[K[i]], S);
V.push_back(make_tuple(mid[K[i]], cx, life));
life = 0;
break;
}
}
if (life >= 1) return 0;
/*cout << "Current State" << endl;
for (int j = 0; j < V.size(); j++) {
cout << "# "<< j << " : L = " << get<0>(V[j]) << ", R = " << get<1>(V[j]) << ", X = " << get<2>(V[j]) << endl;
}*/
}
return 1;
}
