| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1057079 | Sharky | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 1000 tasks!
// 唔算太難 但我見前輩係做呢題上一千嘅
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 8;
const int M = 2e7 + 10;
int n, q, m, node = 1, rt[N], ls[M], rs[M], sum[M];
pair<int, int> p[N];
vector<int> sa[N];
int update(int root, int pos, int l, int r) {
++node;
int x = node;
ls[x] = ls[root], rs[x] = rs[root], sum[x] = sum[root] + 1;
if (l == r) return x;
int mid = (l + r) >> 1;
if (pos <= mid) ls[x] = update(ls[x], pos, l, mid);
else rs[x] = update(rs[x], pos, mid + 1, r);
return x;
}
int query(int ql, int qr, int k, int l, int r) {
if (l == r) return sum[qr] - sum[ql];
int mid = (l + r) >> 1;
if (k <= mid) return sum[rs[qr]] - sum[rs[ql]] + query(ls[ql], ls[qr], k, l, mid);
return query(rs[ql], rs[qr], k, mid + 1, r);
}
int kth(int ql, int qr, int k, int l, int r) {
if (l == r) return l;
int mid = (l + r) >> 1;
int lc = sum[rs[qr]] - sum[rs[ql]];
if (lc >= k) return kth(rs[ql], rs[qr], k, mid + 1, r);
return kth(ls[ql], ls[qr], k - lc, l, mid);
}
struct bar {
int rb, h, rm;
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].first >> p[i].second;
sa[p[i].first].push_back(p[i].second);
}
rt[0] = 1;
for (int i = 1; i <= n; i++) {
rt[i] = rt[i - 1];
for (int& x : sa[i]) rt[i] = update(rt[i], x, 1, n);
}
cin >> q;
while (q--) {
cin >> m;
vector<int> k(m);
for (int i = 0; i < m; i++) cin >> k[i];
sort(k.begin(), k.end());
stack<bar> s;
bool ok = 1;
for (int i = 0; i < m; i++) {
int x = k[i];
while (!s.empty() && s.top().h < x) s.pop();
bar tp = {0, 0, 0};
if (!s.empty()) tp = s.top();
int num = tp.rm + query(rt[tp.rb], rt[x], x, 1, n);
if (num < x) {
ok = 0;
cout << "0\n";
break;
}
if (i < m - 1) {
int height = kth(rt[tp.rb], rt[x], num - tp.rm - x, 1, n);
while (!s.empty() && s.top().h < height) {
s.pop();
bar tp = {0, 0, 0};
if (!s.empty()) tp = s.top();
height = kth(rt[tp.rb], rt[x], num - tp.rm - x, 1, n);
}
s.push({x, height, num - x});
}
}
if (ok) cout << "1\n";
}
}