# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966171 | 2024-04-19T13:20:56 Z | blackslex | Alternating Heights (CCO22_day1problem1) | C++17 | 590 ms | 8228 KB |
#include<bits/stdc++.h> using namespace std; int n, k, q, x, y; int main() { scanf("%d %d %d", &n, &k, &q); vector<int> a(n + 5), dp(n + 5); iota(dp.begin(), dp.end(), 0); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { auto ck = [&] (int l, int r) { vector<vector<int>> v(n + 5, vector<int>()); vector<int> deg(n + 5); for (int i = l; i <= r; i++) { if (i != l && (i & 1) == (l & 1)) v[a[i]].emplace_back(a[i - 1]), deg[a[i - 1]]++; if (i != r && (i & 1) == (l & 1)) v[a[i]].emplace_back(a[i + 1]), deg[a[i + 1]]++; } queue<int> q; for (int i = l; i <= r; i++) if (!deg[a[i]]) q.emplace(a[i]); while (!q.empty()) { int cur = q.front(); q.pop(); for (auto &e: v[cur]) if (!(--deg[e])) q.emplace(e); } for (int i = l; i <= r; i++) if (deg[a[i]]) return 1; return 0; }; int l = i, r = n; while (l <= r) { int mid = (l + r) >> 1; if (!ck(i, mid)) l = mid + 1; else r = mid - 1; } dp[i] = r; } while (q--) scanf("%d %d", &x, &y), printf("%s\n", dp[x] >= y ? "YES" : "NO"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 478 ms | 8228 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 194 ms | 7416 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 590 ms | 572 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 478 ms | 8228 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |