# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259914 | 2020-08-08T19:36:07 Z | Kenzo_1114 | Global Warming (CEOI18_glo) | C++17 | 74 ms | 6520 KB |
#include<bits/stdc++.h> using namespace std; const int MAXN = 200010; const long long int INF = 2e10 + 9; const long long int MAX = 1e9; int n; long long int x, t[MAXN], dp[MAXN], l[MAXN], ans[MAXN]; int main () { scanf("%d %lld", &n, &x); dp[0] = INF; for(int i = 1; i <= n; i++) scanf("%lld", &t[i]), dp[i] = INF; t[0] = -INF; for(int i = 1; i <= n; i++) { int cur = i - 1; while(t[cur] - x >= t[i]) cur = l[cur]; l[i] = cur; } for(int i = 1, mx = 0; i <= n; i++) { int it = lower_bound(dp, dp + n, t[i]) - dp; dp[it] = t[i]; mx = max(mx, it + 1); ans[i] = mx; } dp[0] = INF; for(int i = 1; i <= n; i++) t[i] = MAX - t[i], dp[i] = INF; long long int ANS = 0; for(int i = n; i > 0; i--) { int it = lower_bound(dp, dp + n, t[i]) - dp; dp[it] = t[i]; ANS = max(ANS, it + 1 + ans[l[i]]); } printf("%lld\n", ANS); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 73 ms | 6520 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 1920 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 3512 KB | Output is correct |
2 | Correct | 36 ms | 3448 KB | Output is correct |
3 | Correct | 74 ms | 6520 KB | Output is correct |
4 | Correct | 52 ms | 6520 KB | Output is correct |
5 | Correct | 27 ms | 3456 KB | Output is correct |
6 | Correct | 46 ms | 6268 KB | Output is correct |
7 | Correct | 49 ms | 6264 KB | Output is correct |
8 | Correct | 30 ms | 3516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |