/**
* IOI 2015 - Teams
* Solution using Persistent Segment Tree and Monotonic Stack
* Time Complexity: O((N + sum(M)) * log N)
* Space Complexity: O(N log N)
*/
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 500005;
const int INF = 1e9 + 7;
struct Node {
int sum;
int l, r;
} tree[MAXN * 25];
int root[MAXN];
int node_cnt = 0;
int N_val;
// Build an empty tree
int build(int l, int r) {
int u = ++node_cnt;
tree[u].sum = 0;
if (l == r) return u;
int mid = (l + r) / 2;
tree[u].l = build(l, mid);
tree[u].r = build(mid + 1, r);
return u;
}
// Update the tree persistently
int update(int prev, int l, int r, int pos) {
int u = ++node_cnt;
tree[u] = tree[prev];
tree[u].sum++;
if (l == r) return u;
int mid = (l + r) / 2;
if (pos <= mid)
tree[u].l = update(tree[prev].l, l, mid, pos);
else
tree[u].r = update(tree[prev].r, mid + 1, r, pos);
return u;
}
// Query sum in range [ql, qr]
int query(int u, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[u].sum;
int mid = (l + r) / 2;
return query(tree[u].l, l, mid, ql, qr) + query(tree[u].r, mid + 1, r, ql, qr);
}
// Function to find the smallest x such that:
// Count(A <= x, y_low <= B <= y_high) >= val
// This binary searches over the versions of the persistent tree (roots).
int find_split(int val, int y_low, int y_high) {
int l = 1, r = N_val;
int ans = N_val + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (query(root[mid], 1, N_val, y_low, y_high) >= val) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
void init(int N, int A[], int B[]) {
N_val = N;
// Prepare students sorted by A
vector<pair<int, int>> students(N);
for (int i = 0; i < N; i++) {
students[i] = {A[i], B[i]};
}
sort(students.begin(), students.end());
// Build initial empty tree
root[0] = build(1, N);
// Build persistent versions based on A
// root[x] contains all students with A[i] <= x
int ptr = 0;
for (int x = 1; x <= N; x++) {
root[x] = root[x - 1];
while (ptr < N && students[ptr].first == x) {
root[x] = update(root[x], 1, N, students[ptr].second);
ptr++;
}
}
}
int can(int M, int K[]) {
// Sort the current query requirements
vector<int> k_sorted(M);
for (int i = 0; i < M; i++) k_sorted[i] = K[i];
sort(k_sorted.begin(), k_sorted.end());
// Monotonic Stack
// Stores pair {index_in_k_sorted, split_value_x}
// We use a custom struct or pair
struct Element {
int idx;
int split_val;
};
vector<Element> st;
// Dummy element for the base case (index -1)
// S[-1] is effectively 0. K[-1+1] = K[0].
st.push_back({-1, -INF});
// Used to track sums of team sizes
// We compute prefix sums on the fly or just use current logic
// Using simple accumulation might overflow int if M is large,
// but Constraints say sum of M is small. However, K[i] can be N.
// Sum can exceed 2^31. Use long long.
// But inside the logic, we check differences.
// Let's store prefix sums array.
vector<long long> S(M + 1, 0);
// S[i] = sum(K[0]...K[i]).
// We map index -1 to a virtual S[-1] = 0.
// To simplify, let's just use S[i] as sum of K[0]...K[i].
long long current_S = 0;
for (int i = 0; i < M; i++) {
current_S += k_sorted[i];
S[i] = current_S;
// 1. Check validity using the best constraint from the stack
// We need the stack element whose split_val <= k_sorted[i]
// Since split_val is monotonic in the stack, we can remove elements from the bottom
// if we used a deque, but vector is fine with an index pointer,
// or just binary search / verify the top isn't the only way.
// Actually, since we only add elements with HIGHER split_val,
// and we query with increasing k_sorted[i], we effectively "move right".
// BUT, we are building the stack as we go. The `i` is the query point.
// The stack contains `j < i`.
// We just need to remove elements from the BACK if they are dominated by new `i`.
// But for querying the validity of `i` itself, we look at the stack constructed so far.
// The active constraint is the one with highest split_val <= k_sorted[i].
// Since we cleaned the stack in previous steps, and k is increasing,
// we might need to search. However, usually the stack top or near top is relevant?
// No, the stack stores history. We need binary search on the stack.
// Wait, the standard "Monotonic Stack" for this problem implies we pop from the back
// when adding `i`, but for checking `i`, we use the stack.
// Let's implement binary search on the stack to find the active segment.
int l = 0, r = st.size() - 1;
int best_idx = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (st[mid].split_val <= k_sorted[i]) {
best_idx = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
int j = st[best_idx].idx;
long long S_j = (j == -1) ? 0 : S[j];
// The minimal B requirement for group j+1 ... i is K[j+1]
// Range of B: [K[j+1], N]
// Count available students with A <= K[i] and B >= K[j+1]
int count = query(root[k_sorted[i]], 1, N_val, k_sorted[j + 1], N_val);
if (count < current_S - S_j) {
return 0;
}
// 2. Add current i to stack
// We need to determine where `i` dominates the current stack top.
while (true) {
int top_idx = st.back().idx;
// Compare i with top_idx
// We want to find smallest x such that:
// Count(A <= x, B in [K[top_idx+1], K[i+1] - 1]) >= S[i] - S[top_idx]
// Range B:
int y_low = k_sorted[top_idx + 1];
int y_high = k_sorted[i + 1] - 1;
// Note: if i was the last element, we don't add it to stack?
// The problem loops 0..M-1. We need to add i to stack if i < M-1.
// Because j serves as the "start of a range" for FUTURE queries.
// If i is the last element, it won't be a 'j' for anyone.
if (i == M - 1) break;
long long diff = S[i] - ((top_idx == -1) ? 0 : S[top_idx]);
// If the range is invalid (y_low > y_high), it means K[top+1] > K[i+1]-1.
// Since K is sorted, K[top+1] <= K[i+1].
// If K[top+1] == K[i+1], range is empty, count is 0.
// If diff > 0, split becomes INF.
int split = find_split((int)diff, y_low, y_high);
if (split <= st.back().split_val) {
st.pop_back();
if (st.empty()) {
// Should not happen given dummy -1, but for safety
st.push_back({i, split});
break;
}
} else {
st.push_back({i, split});
break;
}
}
}
return 1;
}
// Helper for the local testing environment or grader
// This part is conditional based on whether main() is provided by grader
#ifdef LOCAL_TEST
int main() {
int N;
if (!(cin >> N)) return 0;
vector<int> A(N), B(N);
for(int i=0; i<N; i++) cin >> A[i] >> B[i];
init(N, A.data(), B.data());
int Q;
cin >> Q;
while(Q--) {
int M;
cin >> M;
vector<int> K(M);
for(int i=0; i<M; i++) cin >> K[i];
cout << can(M, K.data()) << endl;
}
return 0;
}
#endif
