#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
// Persistent Segment Tree
struct Node {
int l, r;
int sum;
} tree[MAXN * 25]; // Sufficient size for N log N updates
int root[MAXN];
int cnt_nodes = 0;
int N_val;
// Standard Persistent Segment Tree Update
void update(int &node, int prev_node, int l, int r, int idx) {
node = ++cnt_nodes;
tree[node] = tree[prev_node];
tree[node].sum++;
if (l == r) return;
int mid = (l + r) / 2;
if (idx <= mid) update(tree[node].l, tree[prev_node].l, l, mid, idx);
else update(tree[node].r, tree[prev_node].r, mid + 1, r, idx);
}
// Range Sum Query
int query(int node, int l, int r, int ql, int qr) {
if (ql > qr || !node) return 0;
if (ql <= l && r <= qr) return tree[node].sum;
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid) res += query(tree[node].l, l, mid, ql, qr);
if (qr > mid) res += query(tree[node].r, mid + 1, r, ql, qr);
return res;
}
// Helper to count students with A in (a_min, a_max] and B in [b_min, N]
int get_count(int a_min, int a_max, int b_min) {
if (a_min >= a_max) return 0;
if (b_min > N_val) return 0;
return query(root[a_max], 1, N_val, b_min, N_val) - query(root[a_min], 1, N_val, b_min, N_val);
}
void init(int N, int A[], int B[]) {
N_val = N;
cnt_nodes = 0;
// Organize students by their minimum team size A[i]
vector<vector<int>> by_A(N + 1);
for (int i = 0; i < N; i++) {
by_A[A[i]].push_back(B[i]);
}
// Build Persistent Segment Tree
// root[i] stores version containing all students with A <= i
root[0] = 0;
for (int i = 1; i <= N; i++) {
root[i] = root[i-1];
for (int b_val : by_A[i]) {
int new_root;
update(new_root, root[i], 1, N, b_val);
root[i] = new_root;
}
}
}
struct Project {
int k, m;
};
// Stack element to maintain the lower envelope of feasibility
struct Element {
int p_idx; // Index in the unique projects array
long long dp_val; // The 'slack' available after satisfying projects up to p_idx
};
int can(int M, int K[]) {
// 1. Sort and group projects by size
vector<int> rawK;
for(int i = 0; i < M; ++i) rawK.push_back(K[i]);
sort(rawK.begin(), rawK.end());
vector<Project> projects;
for(int i = 0; i < M; ) {
int j = i;
int sum_m = 0;
while(j < M && rawK[j] == rawK[i]) {
sum_m += rawK[i]; // Demand is sum of sizes
j++;
}
projects.push_back({rawK[i], sum_m});
i = j;
}
// 2. Process projects using Stack
vector<Element> st;
for (int i = 0; i < projects.size(); ++i) {
int k_curr = projects[i].k;
long long m_curr = projects[i].m;
// Check if current constraint K dominates previous stack elements
while (!st.empty()) {
int top_idx = st.back().p_idx;
long long top_dp = st.back().dp_val;
int prev_idx = (st.size() > 1) ? st[st.size() - 2].p_idx : -1;
int k_prev = (prev_idx == -1) ? 0 : projects[prev_idx].k;
int k_top = projects[top_idx].k;
// Calculate students in A range (k_prev, k_top] that are valid for k_top
// but become INVALID for k_curr because their B is too small ( < k_curr )
int lost = get_count(k_prev, k_top, k_top) - get_count(k_prev, k_top, k_curr);
long long prev_dp = (st.size() > 1) ? st[st.size() - 2].dp_val : 0;
// If the slack at top (projected to new constraint) is worse than or equal to
// the slack at prev, then 'top' is dominated and we merge it.
if (top_dp - lost <= prev_dp) {
st.pop_back();
} else {
break;
}
}
// 3. Calculate new slack for current project
int prev_idx = st.empty() ? -1 : st.back().p_idx;
int k_prev = (prev_idx == -1) ? 0 : projects[prev_idx].k;
long long prev_dp = st.empty() ? 0 : st.back().dp_val;
// New slack = Slack from previous + Newly available students - Demand
// Newly available = Students with A in (k_prev, k_curr] and B >= k_curr
int gained = get_count(k_prev, k_curr, k_curr);
long long new_dp = prev_dp + gained - m_curr;
if (new_dp < 0) return 0; // Impossible to satisfy
st.push_back({i, new_dp});
}
return 1;
}
