#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Memory pool for Persistent Segment Tree
// N up to 500,000. logN ~ 19. 2*N*19 nodes approx. 20M is safe.
const int MAX_NODES = 20000000;
const int MAX_N = 500005;
struct Node {
int sum;
int left, right;
} tree[MAX_NODES];
int root[MAX_N];
int pst_cnt = 0;
int N_val;
// Build an initial empty segment tree
int build(int l, int r) {
int id = ++pst_cnt;
tree[id].sum = 0;
if (l == r) {
tree[id].left = tree[id].right = 0;
return id;
}
int mid = (l + r) / 2;
tree[id].left = build(l, mid);
tree[id].right = build(mid + 1, r);
return id;
}
// Create a new version of the tree with value at pos incremented
int update(int prev_node, int l, int r, int pos) {
int id = ++pst_cnt;
tree[id] = tree[prev_node]; // Copy data from previous version
tree[id].sum++;
if (l == r) return id;
int mid = (l + r) / 2;
if (pos <= mid) {
tree[id].left = update(tree[prev_node].left, l, mid, pos);
} else {
tree[id].right = update(tree[prev_node].right, mid + 1, r, pos);
}
return id;
}
// Query the sum in range [ql, qr]
int query(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[node].sum;
int mid = (l + r) / 2;
return query(tree[node].left, l, mid, ql, qr) +
query(tree[node].right, mid + 1, r, ql, qr);
}
// Initialization function required by the problem
void init(int N, int A[], int B[]) {
N_val = N;
pst_cnt = 0;
// Group students by their minimum team size A[i]
// Indices are 1-based, array is 0-based
vector<vector<int>> students_by_A(N + 1);
for (int i = 0; i < N; ++i) {
students_by_A[A[i]].push_back(B[i]);
}
// Build base tree (version 0)
root[0] = build(1, N);
// Build persistent versions. root[i] contains all students with A <= i.
for (int i = 1; i <= N; ++i) {
root[i] = root[i-1];
for (int b_val : students_by_A[i]) {
root[i] = update(root[i], 1, N, b_val);
}
}
}
// Function to check if valid assignment is possible for the day
int can(int M, int K[]) {
// Sort project requirements
vector<int> sorted_K(M);
for(int i = 0; i < M; ++i) sorted_K[i] = K[i];
sort(sorted_K.begin(), sorted_K.end());
struct Element {
int k_val; // The project size constraint A <= k_val
int y_val; // The B-value up to which students are used
};
// Stack maintains the "boundary" of used students.
// {0, N_val} acts as a sentinel representing the entire available space initially.
vector<Element> st;
st.push_back({0, N_val});
for (int k : sorted_K) {
// Since k increases, any previously used block that ended before k (y_val < k)
// is no longer relevant as a restriction because we only care about B >= k.
while (st.size() > 1 && st.back().y_val < k) {
st.pop_back();
}
int demand = k;
int last_start = k; // We start looking for students with B >= k
// Try to satisfy 'demand' by merging stack segments or filling gaps
while (true) {
if (st.empty()) return 0; // Should not happen due to sentinel, unless N < k (impossible)
Element top = st.back();
// We search in the range [last_start, top.y_val].
// If last_start > top.y_val, this segment is fully consumed/skipped.
if (last_start > top.y_val) {
st.pop_back();
continue;
}
// Calculate number of available students in [last_start, top.y_val] with A <= k.
// "Available" means: Total in range (A <= k) MINUS Already used (A <= top.k_val).
// root[top.k_val] represents the usage profile of the stack top.
int added_capacity = query(root[k], 1, N_val, last_start, top.y_val)
- query(root[top.k_val], 1, N_val, last_start, top.y_val);
if (added_capacity >= demand) {
// We can satisfy the remaining demand within this segment.
// Binary search to find the smallest Y such that we take exactly 'demand' students.
int low = last_start, high = top.y_val;
int ans = high;
while (low <= high) {
int mid = low + (high - low) / 2;
int cap = query(root[k], 1, N_val, last_start, mid)
- query(root[top.k_val], 1, N_val, last_start, mid);
if (cap >= demand) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
// We found the new boundary Y = ans.
// This project effectively consumes students up to ans.
st.push_back({k, ans});
break; // Done with this project
} else {
// Not enough students in this segment. Take all of them and continue.
demand -= added_capacity;
last_start = top.y_val + 1;
st.pop_back(); // Remove this segment as we've "surpassed" it
// Check if we exhausted everything including sentinel
if (st.empty() && demand > 0) return 0;
}
}
}
return 1;
}
