QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750708 | #6392. Curtains | IBory | 0 | 49ms | 21752kb | C++20 | 1.8kb | 2024-11-15 15:34:24 | 2024-11-15 15:34:25 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int SZ = 1 << 19;
vector<int> SR[SZ];
vector<pii> QR[SZ];
int ans[SZ];
struct Seg {
pii T[SZ << 1];
pii Merge(pii a, pii b) {
if (!a.first || !b.first) return max(a, b);
if (b.second < 0) return a;
// cout << a.first << ' ' << a.second << " + " << b.first << ' ' << b.second << " = ";
if (a.second + 1 < b.first) {
// cout << a.first << ' ' << a.second << '\n';
return a;
}
// cout << a.first << ' ' << max(a.second, b.second) << '\n';
return {a.first, max(a.second, b.second)};
}
Seg() {
for (int i = 1; i <= SZ; ++i) T[i + SZ - 1] = {i, -1};
for (int i = SZ - 1; i > 0; --i) T[i] = Merge(T[i * 2], T[i * 2 + 1]);
}
void Update(int i, int n) {
i += SZ - 1;
T[i].first = i - SZ + 1;
T[i].second = max(T[i].second, n);
// cout << "upd: " << T[i].first << ' ' << T[i].second << '\n';
while (i >>= 1) T[i] = Merge(T[i * 2], T[i * 2 + 1]);
}
pii Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
if (R < sL || sR < L) return {0, 0};
if (L <= sL && sR <= R) return T[n];
int mid = (sL + sR) >> 1;
return Merge(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
}
} T;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int M, N, Q;
cin >> M >> N >> Q;
for (int i = 1; i <= N; ++i) {
int l, r;
cin >> l >> r;
SR[r].push_back(l);
}
for (int i = 1; i <= Q; ++i) {
int l, r;
cin >> l >> r;
QR[r].emplace_back(l, i);
}
for (int i = 1; i <= M; ++i) {
for (int l : SR[i]) T.Update(l, i);
for (auto [l, id] : QR[i]) {
pii p = T.Query(l, i);
// cout << l << ' ' << i << " / " << p.first << ' ' << p.second << '\n';
ans[id] = (p == pii{l, i});
}
}
for (int i = 1; i <= Q; ++i) cout << (ans[i] ? "YES" : "NO") << '\n';
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 13212kb
input:
200 200 200 113 134 77 77 110 143 126 157 122 131 161 172 59 134 19 68 117 142 15 103 61 182 12 67 73 97 72 128 68 110 19 137 14 118 60 150 42 64 25 30 118 158 149 164 79 149 21 94 33 82 3 130 36 142 57 170 64 140 40 98 115 132 2 45 27 85 43 181 120 125 82 160 121 176 16 154 59 74 34 52 71 74 57 185...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO N...
result:
wrong answer 2nd lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 49ms
memory: 21752kb
input:
100000 100000 100000 44237 85021 45776 80409 39632 94735 28119 63770 47399 73347 28902 87358 27924 65499 23898 54817 50114 96633 11325 37690 46642 94643 9271 47594 47324 47948 27957 58134 20443 88720 20834 89483 77577 94705 7835 30030 37387 59648 8364 76478 66145 76025 12683 79475 1745 33181 43966 5...
output:
NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%