#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "teams.h"
struct Node {
int cnt;
int L, R;
}tree[500005 * 42];
int root[500005];
int node_cnt;
int upd(int prev_node, int l, int r, int val) {
int curr = ++node_cnt;
tree[curr] = tree[prev_node];
tree[curr].cnt++;
if(l == r) return curr;
int m = l + r >> 1;
if(val <= m)
tree[curr].L = upd(tree[prev_node].L, l, m, val);
else
tree[curr].R = upd(tree[prev_node].R, m + 1, r, val);
return curr;
}
int qry(int node_l, int node_r, int l, int r, int ql, int qr) {
if(ql > r || qr < l || node_r == node_l) return 0;
if(ql <= l && r <= qr) return tree[node_r].cnt - tree[node_l].cnt;
int m = l + r >> 1;
return qry(tree[node_l].L, tree[node_r].L, l, m, ql, qr) +
qry(tree[node_l].R, tree[node_r].R, m + 1, r, ql, qr);
}
struct S {
int A, B;
bool operator<(const S &other) const {
return A < other.A;
}
};
int tot_S;
vector<S> st;
int cnt_st(int mxA, int mnB) {
if(mxA < 1 || mnB > tot_S) return 0;
return qry(root[0], root[mxA], 1, tot_S, mnB, tot_S);
}
void init(int N, int A[], int B[]) {
tot_S = N;
st.resize(N);
for(int i = 0; i < N; i++) {
st[i] = {A[i], B[i]};
}
sort(st.begin(), st.end());
int sid = 0;
for(int i = 1; i <= N; i++) {
root[i] = root[i - 1];
while(sid < N && st[sid].A == i) {
root[i] = upd(root[i], 1, N, st[sid].B);
sid++;
}
}
}
struct State {
int k_val, dp_val, j;
};
int get_val(const State &s, int x) {
return s.dp_val + cnt_st(x, x) - cnt_st(s.k_val, x);
}
int can(int M, int K[]) {
ll sum = accumulate(K, K + M, 0LL);
if(sum > tot_S)
return 0;
sort(K, K + M);
vector<State> dq;
dq.push_back({0, 0, tot_S});
int head = 0;
for(int i = 0; i < M; ++i) {
int curr = K[i];
while(dq.size() - head > 1 && dq[head].j < curr) {
head++;
}
int curr_dp = get_val(dq[head], curr) - curr;
if(curr_dp < 0) return 0;
State nstate = {curr, curr_dp, 0};
while(dq.size() > head) {
State &top = dq.back();
if(get_val(nstate, top.j) <= get_val(top, top.j)) {
if(head == dq.size() - 1) {
top = nstate;
top.j = tot_S;
goto next_i;
}
dq.erase(dq.begin() + head);
}
else {
int l = curr, r = top.j, res = curr - 1;
while(l <= r) {
int m = l + r >> 1;
if(get_val(nstate, m) <= get_val(top, m)) {
res = m;
l = m + 1;
}
else
r = m - 1;
}
if(res >= curr) {
nstate.j = res;
dq.insert(dq.begin() + head, nstate);
}
break;
}
}
next_i:;
}
return 1;
}
