#include "teams.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#include <stack>
#include <functional>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
using ll = long long;
const int MN = 5e5+10;
const int MQ = 2e5+10;
const int MX = MN * 20; // turn up when submit
int N, A[MN], B[MN], ord[MN];
int sv[MX], sl[MX], sr[MX], X, root[MN];
int nn(int p=0)
{
++X;
assert(X<MX);
if(p!=0)
sv[X]=sv[p], sl[X]=sl[p], sr[X]=sr[p];
return X;
}
void upd(int &n, int l, int r, int q)
{
n=nn(n);
++sv[n];
if(r-l>1)
{
int m=l+(r-l)/2;
if(q<m) upd(sl[n], l, m, q);
else upd(sr[n], m, r, q);
}
}
int qry(int n, int l, int r, int ql, int qr)
{
if(n==0) return 0;
if(ql <= l&&r <= qr) return sv[n];
else
{
int m=l+(r-l)/2, f=0;
if(ql < m) f += qry(sl[n], l, m, ql, qr);
if(m < qr) f += qry(sr[n], m, r, ql, qr);
return f;
}
}
int get(int l1, int l2, int r1, int r2) // (l1, l2], [r1, r2)
{
if(r1>=r2) return 0;
return qry(root[l2], 1, N+1, r1, r2)-qry(root[l1], 1, N+1, r1, r2);
}
int qry2(int u, int v, int l, int r, int ql, int q)// pos if answer, neg if fails to reach
{
if(q==0) return l;
if(ql <= l&&sv[v]-sv[u]<q) return sv[u]-sv[v];
if(r-l>1)
{
int m=l+(r-l)/2, vl=0;
if(ql < m) vl=qry2(sl[u], sl[v], l, m, ql, q);
if(vl > 0) return vl;
int ans = qry2(sr[u], sr[v], m, r, ql, q+vl);
if(ans>0) return ans;
return ans+vl;
}
else
return r;
}
int find(int l1, int l2, int r1, int q)
{ // returns smallest r2, where get(l1, l2, r1, r2) >= q
return qry2(root[l1], root[l2], 1, N+1, r1, q);
}
void init(int _N, int _A[], int _B[]) {
N=_N;
memcpy(A, _A, N*sizeof*_A);
memcpy(B, _B, N*sizeof*_B);
std::iota(ord, ord+N, 0);
std::sort(ord, ord+N, [&](int u, int v){return A[u]<A[v];});
for(int i=1, j=0;i<=N;++i)
{
root[i] = root[i-1];
for(;j < N && A[ord[j]] == i;++j)
upd(root[i], 1, N+1, B[ord[j]]);
}
}
struct obj
{
public:
int l, r, spare; // (l, cur] x [cur, r) queried. Spare remain from [r-1, r)
};
int can(int M, int K[]) {
std::sort(K, K+M);
{
ll sum=0;
for(int i=0;i<M;++i) sum += K[i];
if(sum > N) return 0;
}
std::vector<int> w;
{
int M2=0;
for(int i=0;i<M;++i)
{
if(i==0||K[i]!=K[i-1])
w.push_back(0), ++M2;
w.back() += K[i];
K[M2-1]=K[i];
}
M=M2;
}
std::stack<obj> stk;
stk.push({0, N+1, 0});
for(int i=0;i<M;++i)
{
int cur = K[i];
int cur_L = cur;
for(;;)
{
if(stk.empty()) return 0;
if(stk.top().r == cur || ckmax(stk.top().r, cur)) stk.top().spare=0;
int v = get(stk.top().l, cur, cur_L, stk.top().r-1);
if(v < w[i])
{
int v2 = get(stk.top().l, cur, cur_L, stk.top().r);
if(v2+stk.top().spare>=w[i])
{
stk.top().spare+=v2-w[i];
stk.top().l = cur;
break;
}
else
{
w[i] -= v2+stk.top().spare;
cur_L = stk.top().r;
stk.pop();
}
}
else
{
int r = find(stk.top().l, cur, cur_L, w[i]);
assert(cur_L <= r && r < stk.top().r);
int v2 = get(stk.top().l, cur, cur_L, r);
assert(v2 >= w[i]);
stk.push({cur, r, v2-w[i]});
break;
}
}
}
return 1;
}
