// M
#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
const int N = 500005, MXS = N * 20;
int n, A[N], B[N], K[N];
int ts, root[N], L[MXS], R[MXS], C[MXS];
vector < int > U, V[N];
int Add(int i, int id, int l = 1, int r = n + 1)
{
int ID = ++ ts;
L[ID] = L[id];
R[ID] = R[id];
C[ID] = C[id] + 1;
if (r - l < 2)
return ID;
if (i < ((l + r) >> 1))
L[ID] = Add(i, L[id], l, (l + r) >> 1);
else
R[ID] = Add(i, R[id], (l + r) >> 1, r);
return ID;
}
int Count(int lid, int rid, int le, int ri, int l = 1, int r = n + 1)
{
if (ri <= l || r <= le)
return 0;
if (le <= l && r <= ri)
return C[rid] - C[lid];
return Count(L[lid], L[rid], le, ri, l, (l + r) >> 1) + Count(R[lid], R[rid], le, ri, (l + r) >> 1, r);
}
int GetKth(int lid, int rid, int &k, int l = 1, int r = n + 1)
{
if (C[rid] - C[lid] < k)
return n + 1;
if (r - l < 2)
return l;
if (C[L[rid]] - C[L[lid]] >= k)
return GetKth(L[lid], L[rid], k, l, (l + r) >> 1);
k -= C[L[rid]] - C[L[lid]];
return GetKth(R[lid], R[rid], k, (l + r) >> 1, r);
}
void init(int _n, int _A[], int _B[])
{
n = _n;
vector < int > P(n);
for (int i = 0; i < n; i ++)
P[i] = i;
sort(P.begin(), P.end(), [&](int i, int j){return make_pair(_B[i], _A[i]) < make_pair(_B[j], _A[j]);});
U.push_back(0);
for (int i = 0; i < n; i ++)
U.push_back(_B[P[i]]);
for (int i = 1; i <= n; i ++)
A[i] = _A[P[i - 1]], B[i] = i;
for (int i = 1; i <= n; i ++)
V[A[i]].push_back(i);
for (int i = 1; i <= n; i ++)
{
root[i] = root[i - 1];
for (int j : V[i])
root[i] = Add(B[j], root[i]);
}
}
int can(int _m, int _K[])
{
int m = _m;
for (int i = 1; i <= m; i ++)
K[i] = _K[i - 1];
sort(K + 1, K + m + 1);
vector < pair < int , int > > Stk;
Stk.push_back({0, n + 1});
for (int i = 1; i <= m; i ++)
{
int need = K[i];
int le = lower_bound(U.begin(), U.end(), K[i]) - U.begin();
int ri = le;
while (Stk.size() && need > 0)
{
int c = Count(root[Stk.back().first], root[K[i]], ri, Stk.back().second);
if (c >= need)
break;
need -= c;
ri = max(ri, Stk.back().second);
Stk.pop_back();
}
if (!Stk.size())
return 0;
assert(need);
int c = Count(root[Stk.back().first], root[K[i]], 1, ri);
need += c;
ri = GetKth(root[Stk.back().first], root[K[i]], need);
if (ri > n)
return 0;
ri ++;
assert(ri <= Stk.back().second);
Stk.push_back({K[i], ri});
}
return 1;
}
