| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1309950 | jg86 | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct Node {
int l, r;
int sum;
};
static int N;
static vector<int> roots;
static vector<Node> seg;
static size_t baseSizeAfterInit;
static inline int clone_node(int from) {
seg.push_back(seg[from]);
return (int)seg.size() - 1;
}
static int update_point(int node, int l, int r, int pos) {
int n = clone_node(node);
if (l == r) {
seg[n].sum++;
return n;
}
int mid = (l + r) >> 1;
if (pos <= mid) seg[n].l = update_point(seg[n].l, l, mid, pos);
else seg[n].r = update_point(seg[n].r, mid + 1, r, pos);
seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
return n;
}
static int query_diff(int pref, int used, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return seg[pref].sum - seg[used].sum;
int mid = (l + r) >> 1;
return query_diff(seg[pref].l, seg[used].l, l, mid, ql, qr) +
query_diff(seg[pref].r, seg[used].r, mid + 1, r, ql, qr);
}
static int consume_suffix(int pref, int used, int l, int r, int start, int &need) {
if (need == 0 || r < start) return used;
if (l >= start) {
int avail = seg[pref].sum - seg[used].sum;
if (avail == 0) return used;
if (avail <= need) {
need -= avail;
return pref;
}
if (l == r) {
int n = clone_node(used);
seg[n].sum += need;
need = 0;
return n;
}
}
if (l == r) return used;
int mid = (l + r) >> 1;
int n = clone_node(used);
if (start <= mid)
seg[n].l = consume_suffix(seg[pref].l, seg[used].l, l, mid, start, need);
else
seg[n].l = seg[used].l;
seg[n].r = consume_suffix(seg[pref].r, seg[used].r, mid + 1, r, start, need);
seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
return n;
}
void init(int N_, int A[], int B[]) {
N = N_;
vector<pair<int,int>> students;
students.reserve(N);
for (int i = 0; i < N; i++) students.push_back({A[i], B[i]});
sort(students.begin(), students.end());
size_t reserveNodes = 1ull + 20ull * (size_t)N + 8000000ull;
seg.clear();
seg.reserve(reserveNodes);
seg.push_back({0, 0, 0});
roots.assign(N + 1, 0);
int idx = 0;
for (int s = 1; s <= N; s++) {
int root = roots[s - 1];
while (idx < N && students[idx].first == s) {
root = update_point(root, 1, N, students[idx].second);
idx++;
}
roots[s] = root;
}
baseSizeAfterInit = seg.size();
}
int can(int M, int K[]) {
vector<int> v;
v.reserve(M);
long long total = 0;
for (int i = 0; i < M; i++) {
v.push_back(K[i]);
total += K[i];
if (total > N) return 0;
}
sort(v.begin(), v.end());
int used = 0;
for (int i = 0; i < M; ) {
int s = v[i];
int cnt = 1;
while (i + cnt < M && v[i + cnt] == s) cnt++;
long long need_ll = 1LL * s * cnt;
int need = (int)need_ll;
int pref = roots[s];
int avail = query_diff(pref, used, 1, N, s, N);
if (avail < need) {
seg.resize(baseSizeAfterInit);
return 0;
}
int rem = need;
used = consume_suffix(pref, used, 1, N, s, rem);
i += cnt;
}
seg.resize(baseSizeAfterInit);
return 1;
}
struct FastScanner {
static constexpr int BUFSIZE = 1 << 20;
int idx = 0, size = 0;
char buf[BUFSIZE];
inline char read() {
if (idx >= size) {
size = (int)fread(buf, 1, BUFSIZE, stdin);
idx = 0;
if (size == 0) return 0;
}
return buf[idx++];
}
int nextInt() {
char c;
do {
c = read();
if (!c) return 0;
} while (c <= ' ');
int x = 0;
while (c > ' ') {
x = x * 10 + (c - '0');
c = read();
}
return x;
}
};
int main() {
FastScanner fs;
int n = fs.nextInt();
if (!n) return 0;
vector<int> A(n), B(n);
for (int i = 0; i < n; i++) {
A[i] = fs.nextInt();
B[i] = fs.nextInt();
}
init(n, A.data(), B.data());
int Q = fs.nextInt();
string out;
out.reserve(Q * 2);
vector<int> K;
for (int qi = 0; qi < Q; qi++) {
int M = fs.nextInt();
K.resize(M);
for (int i = 0; i < M; i++) K[i] = fs.nextInt();
int ans = can(M, K.data());
out.push_back(char('0' + ans));
out.push_back('\n');
}
fwrite(out.c_str(), 1, out.size(), stdout);
return 0;
}