# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
120014 | 2019-06-23T02:19:29 Z | E869120 | Editor (BOI15_edi) | C++14 | 3000 ms | 34616 KB |
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <queue> #include <functional> using namespace std; #pragma warning (disable: 4996) int N, A[1 << 19], G[1 << 19], level[1 << 19], par[1 << 19], maxlevel = 0; vector<int>I[1 << 19]; set<int>Set; priority_queue<int, vector<int>, less<int>> Q; int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &A[i]); level[i] = max(0, -A[i]); maxlevel = max(maxlevel, level[i]); I[level[i]].push_back(i); } for (int i = 1; i <= N; i++) Set.insert(i); for (int i = maxlevel; i >= 1; i--) { set<int>Set2; for (int j = 0; j < I[i].size(); j++) { auto itr = Set.lower_bound(I[i][j]); if (itr != Set.end() && (*itr) == I[i][j]) { Set.erase(I[i][j]); Set2.insert(I[i][j]); } } for (int j = 0; j < I[i].size(); j++) { auto itr = Set.lower_bound(I[i][j]); itr--; par[I[i][j]] = (*itr); auto itr2 = Set2.lower_bound(I[i][j]); if (itr2 != Set2.end() && (*itr2) == I[i][j]) Set.erase(par[I[i][j]]); } } Q.push(0); G[0] = 1; for (int i = 1; i <= N; i++) { if (A[i] > 0) { G[i] = 1; Q.push(i); } else { G[i] = 1; int cx = i; while (par[cx] != 0) { cx = par[cx]; G[cx] ^= 1; } Q.push(cx); while (!Q.empty()) { int pos = Q.top(); if (G[pos] == 0) Q.pop(); else break; } } int ans = Q.top(); printf("%d\n", A[ans]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 12672 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 272 ms | 34616 KB | Output is correct |
2 | Correct | 275 ms | 34532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 169 ms | 23372 KB | Output is correct |
2 | Execution timed out | 3044 ms | 25960 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 12672 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |