# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
522075 | 2022-02-03T18:36:35 Z | LucaDantas | Global Warming (CEOI18_glo) | C++17 | 2000 ms | 118016 KB |
#include <cstdio> #include <cstring> #include <map> #include <algorithm> constexpr int maxn = 2e5+10; constexpr unsigned int maxT = 0x7fffffff; struct BIT { std::map<int, int> bit; void upd(unsigned int x, int v) { for(x++; x < maxT; x += x&-x) bit[x] = std::max(bit[x], v); } int query(int x) { int ans = 0; for(x++; x > 0; x -= x&-x) ans = std::max(ans, bit[x]); return ans; } void clear() { bit.clear(); } } bit; int t[maxn], dp[maxn], max_temp; int main() { int n, x; scanf("%d %d", &n, &x); for(int i = 0; i < n; i++) scanf("%d", t+i), max_temp = std::max(max_temp, t[i]); for(int i = 0; i < n; i++) { dp[i] = bit.query(t[i]-1)+1; bit.upd(t[i], dp[i]); } bit.clear(); int ans = 0; std::reverse(t, t+n); std::reverse(dp, dp+n); for(int i = 0; i < n; i++) t[i] = max_temp - t[i] + 1; for(int i = 0; i < n; i++) { ans = std::max(ans, dp[i] + bit.query(t[i] + x - 1)); bit.upd(t[i], bit.query(t[i]-1)+1); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 12 ms | 1660 KB | Output is correct |
20 | Correct | 11 ms | 1484 KB | Output is correct |
21 | Correct | 12 ms | 1356 KB | Output is correct |
22 | Correct | 10 ms | 1236 KB | Output is correct |
23 | Correct | 7 ms | 844 KB | Output is correct |
24 | Correct | 7 ms | 844 KB | Output is correct |
25 | Correct | 2 ms | 332 KB | Output is correct |
26 | Correct | 5 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2097 ms | 118016 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 919 ms | 36980 KB | Output is correct |
2 | Correct | 911 ms | 37136 KB | Output is correct |
3 | Correct | 904 ms | 36940 KB | Output is correct |
4 | Correct | 375 ms | 19992 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 260 ms | 2920 KB | Output is correct |
7 | Correct | 544 ms | 25724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2097 ms | 85824 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 0 ms | 204 KB | Output is correct |
11 | Correct | 0 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 12 ms | 1660 KB | Output is correct |
20 | Correct | 11 ms | 1484 KB | Output is correct |
21 | Correct | 12 ms | 1356 KB | Output is correct |
22 | Correct | 10 ms | 1236 KB | Output is correct |
23 | Correct | 7 ms | 844 KB | Output is correct |
24 | Correct | 7 ms | 844 KB | Output is correct |
25 | Correct | 2 ms | 332 KB | Output is correct |
26 | Correct | 5 ms | 332 KB | Output is correct |
27 | Execution timed out | 2097 ms | 118016 KB | Time limit exceeded |
28 | Halted | 0 ms | 0 KB | - |