# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44640 | 2018-04-04T06:14:57 Z | RayaBurong25_1 | Editor (BOI15_edi) | C++17 | 361 ms | 66036 KB |
#include <stdio.h> #include <vector> int Val[300005]; typedef struct node node; struct node { int level[20]; int last; int next[20]; }; node Last[300005]; // std::vector<std::pair<int, int> > Last[300005]; int max(int a, int b) { return (a > b)?a:b; } int main() { int N; scanf("%d", &N); int i, x; // std::vector<std::pair<int, int> >::iterator it; int j, k; for (i = 1; i <= N; i++) { scanf("%d", &x); if (x > 0) { Val[i] = x; // Last[i] = Last[i - 1]; // Last[i].push_back({0, i - 1}); // Last[i] = {0, i - 1, i - 1}; Last[i].level[0] = 0; Last[i].last = i - 1; Last[i].next[0] = i - 1; for (k = 1; k < 20; k++) { Last[i].level[k] = max(Last[i].level[k - 1], Last[Last[i].next[k - 1]].level[k - 1]); Last[i].next[k] = Last[Last[i].next[k - 1]].next[k - 1]; } printf("%d\n", Val[i]); } else { // it = Last[i - 1].end(); // it--; // while (it->first <= x) it--; j = i - 1; for (k = 19; k >= 0; k--) { if (Last[j].level[k] <= x) { j = Last[j].next[k]; } } // j = i - 1; // while (Last[j].level <= x) j = Last[j].next; j = Last[j].last; Val[i] = Val[j]; // Last[i] = Last[it->second]; // Last[i].push_back({x, i - 1}); // Last[i] = {x, i - 1, j}; Last[i].level[0] = x; Last[i].last = i - 1; Last[i].next[0] = j; for (k = 1; k < 20; k++) { Last[i].level[k] = max(Last[i].level[k - 1], Last[Last[i].next[k - 1]].level[k - 1]); Last[i].next[k] = Last[Last[i].next[k - 1]].next[k - 1]; } printf("%d\n", Val[i]); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 1128 KB | Output is correct |
3 | Correct | 2 ms | 1128 KB | Output is correct |
4 | Correct | 2 ms | 1128 KB | Output is correct |
5 | Correct | 4 ms | 1312 KB | Output is correct |
6 | Correct | 2 ms | 1312 KB | Output is correct |
7 | Correct | 4 ms | 1336 KB | Output is correct |
8 | Correct | 2 ms | 1336 KB | Output is correct |
9 | Correct | 6 ms | 1496 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 213 ms | 51840 KB | Output is correct |
2 | Correct | 160 ms | 51840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 51840 KB | Output is correct |
2 | Correct | 121 ms | 51840 KB | Output is correct |
3 | Correct | 237 ms | 51840 KB | Output is correct |
4 | Correct | 165 ms | 53768 KB | Output is correct |
5 | Correct | 221 ms | 55840 KB | Output is correct |
6 | Correct | 273 ms | 55840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 1128 KB | Output is correct |
3 | Correct | 2 ms | 1128 KB | Output is correct |
4 | Correct | 2 ms | 1128 KB | Output is correct |
5 | Correct | 4 ms | 1312 KB | Output is correct |
6 | Correct | 2 ms | 1312 KB | Output is correct |
7 | Correct | 4 ms | 1336 KB | Output is correct |
8 | Correct | 2 ms | 1336 KB | Output is correct |
9 | Correct | 6 ms | 1496 KB | Output is correct |
10 | Correct | 213 ms | 51840 KB | Output is correct |
11 | Correct | 160 ms | 51840 KB | Output is correct |
12 | Correct | 91 ms | 51840 KB | Output is correct |
13 | Correct | 121 ms | 51840 KB | Output is correct |
14 | Correct | 237 ms | 51840 KB | Output is correct |
15 | Correct | 165 ms | 53768 KB | Output is correct |
16 | Correct | 221 ms | 55840 KB | Output is correct |
17 | Correct | 273 ms | 55840 KB | Output is correct |
18 | Correct | 256 ms | 58488 KB | Output is correct |
19 | Correct | 247 ms | 60460 KB | Output is correct |
20 | Correct | 361 ms | 61376 KB | Output is correct |
21 | Correct | 167 ms | 63940 KB | Output is correct |
22 | Correct | 293 ms | 66036 KB | Output is correct |