/* https://codeforces.com/blog/entry/19454?#comment-243243 (zxqfl) */
#include "teams.h"
#define N 500000
#define M 200000
#define LN 19 /* LN = ceil(log2(N)) */
#define N_ ((N + M * 2) * (LN + 1))
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ii[N], tt[N + 1], n;
int *ll_;
int compare_l(int i, int j) { return ll_[i] - ll_[j]; }
int compare_k(int k1, int k2) { return k1 - k2; }
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int ll[1 + N_], rr[1 + N_], cnt[1 + N_], _ = 1;
int update(int t, int l, int r, int i) {
int t_ = _++;
cnt[t_] = cnt[t] + 1;
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
else
ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
}
return t_;
}
void init(int n_, int ll[], int rr[]) {
int h, i, t;
n = n_;
for (i = 0; i < n; i++)
ii[i] = i;
ll_ = ll, compare = compare_l, sort(ii, 0, n);
for (h = 0, i = 1, t = 0; i <= n; i++) {
while (h < n && ll[ii[h]] == i)
t = update(t, 0, n, rr[ii[h++]] - 1);
tt[i] = t;
}
}
int k_;
int update_(int t1, int t2, int l, int r, int i) {
int m, t_;
if (r <= i || k_ == 0)
return t1;
if (l >= i && k_ >= cnt[t2] - cnt[t1]) {
k_ -= cnt[t2] - cnt[t1];
return t2;
}
t_ = _++;
m = (l + r) / 2;
if (r - l > 1) {
ll[t_] = update_(ll[t1], ll[t2], l, m, i), rr[t_] = update_(rr[t1], rr[t2], m, r, i);
cnt[t_] = cnt[ll[t_]] + cnt[rr[t_]];
} else
cnt[t_] = cnt[t1] + k_, k_ = 0;
return t_;
}
int can(int m, int *kk) {
int i, t;
compare = compare_k, sort(kk, 0, m);
t = 0;
for (i = 0; i < m; i++) {
k_ = kk[i], t = update_(t, tt[kk[i]], 0, n, kk[i] - 1);
if (k_ > 0)
return 0;
}
return 1;
}
