#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
// ------------------------ Segtree Library ----------------------
int size_ = 1;
vector<int> dat[1 << 19];
void initialize(int sz) {
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 lim_x, int num) {
int u = 2; num--;
while (u < size_ * 2) {
int G = counts(u, 0, 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 -----------------------
void init(int N, int A[], int B[]) {
initialize(N);
for (int i = 0; i < N; i++) add(A[i], B[i]);
syncronization();
}
int can(int M, int K[]) {
sort(K, K + M);
int cx = 0, cnt = 0;
for (int i = 0; i < M; i++) {
if (cx < K[i]) { cnt = query(0, K[i] - 1, 0, K[i] - 1); }
else {
if (K[i - 1] + 1 <= K[i] - 1) cnt += query(K[i - 1] + 1, K[i] - 1, K[i - 1] + 1, K[i] - 1);
}
cnt += K[i];
int G = getmin(K[i], cnt);
//cout << "Query : lim_x = " << K[i] << ", cnt = " << cnt << " -> Answer = " << G << endl;
if (G == (1 << 30)) return 0;
cx = G;
}
return 1;
}
