# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
260703 | 2020-08-10T18:31:47 Z | bigg | Global Warming (CEOI18_glo) | C++14 | 85 ms | 7800 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 10; const ll INF =1e18; ll dp[MAXN], v[MAXN], neg[MAXN]; int ans1[MAXN]; int main(){ int n; ll x; scanf("%d %lld", &n, &x); for(int i = 1; i <= n; i++) scanf("%lld", &v[i]), dp[i] = INF, neg[i] = -v[i]; //dp[0] = INF; int ans = -1; for(int i = 0; i <= n; i++) dp[i] = INF; for(int i = 1; i <= n; i++){ int it1 = lower_bound(dp, dp + n, v[i]) - dp; dp[it1] = v[i]; ans1[i] = it1 +1; ans = max(ans, it1 + 1); } for(int i = 0; i <= n; i++) dp[i] = INF; for(int i = n; i; i--){ int it1 = lower_bound(dp, dp + n, neg[i] +x) - dp; int it2 = lower_bound(dp, dp + n, neg[i]) - dp; dp[it2] = neg[i]; ans = max(ans, it1 + ans1[i]); //printf("%d\n", it1 + ans1[i]); } printf("%d\n",ans ); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 0 ms | 384 KB | Output is correct |
13 | Correct | 0 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 0 ms | 384 KB | Output is correct |
13 | Correct | 0 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 1 ms | 384 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 1 ms | 384 KB | Output is correct |
23 | Correct | 1 ms | 384 KB | Output is correct |
24 | Correct | 1 ms | 384 KB | Output is correct |
25 | Correct | 1 ms | 384 KB | Output is correct |
26 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 7672 KB | Output is correct |
2 | Correct | 78 ms | 7672 KB | Output is correct |
3 | Correct | 77 ms | 7672 KB | Output is correct |
4 | Correct | 78 ms | 7672 KB | Output is correct |
5 | Correct | 58 ms | 6904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 2176 KB | Output is correct |
2 | Correct | 22 ms | 2176 KB | Output is correct |
3 | Correct | 22 ms | 2176 KB | Output is correct |
4 | Correct | 16 ms | 2048 KB | Output is correct |
5 | Correct | 0 ms | 384 KB | Output is correct |
6 | Correct | 15 ms | 2048 KB | Output is correct |
7 | Correct | 15 ms | 2176 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 3960 KB | Output is correct |
2 | Correct | 35 ms | 4088 KB | Output is correct |
3 | Correct | 71 ms | 7672 KB | Output is correct |
4 | Correct | 59 ms | 6904 KB | Output is correct |
5 | Correct | 29 ms | 3584 KB | Output is correct |
6 | Correct | 49 ms | 6648 KB | Output is correct |
7 | Correct | 55 ms | 7416 KB | Output is correct |
8 | Correct | 33 ms | 4096 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 0 ms | 384 KB | Output is correct |
13 | Correct | 0 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 1 ms | 384 KB | Output is correct |
21 | Correct | 1 ms | 384 KB | Output is correct |
22 | Correct | 1 ms | 384 KB | Output is correct |
23 | Correct | 1 ms | 384 KB | Output is correct |
24 | Correct | 1 ms | 384 KB | Output is correct |
25 | Correct | 1 ms | 384 KB | Output is correct |
26 | Correct | 1 ms | 384 KB | Output is correct |
27 | Correct | 85 ms | 7672 KB | Output is correct |
28 | Correct | 78 ms | 7672 KB | Output is correct |
29 | Correct | 77 ms | 7672 KB | Output is correct |
30 | Correct | 78 ms | 7672 KB | Output is correct |
31 | Correct | 58 ms | 6904 KB | Output is correct |
32 | Correct | 22 ms | 2176 KB | Output is correct |
33 | Correct | 22 ms | 2176 KB | Output is correct |
34 | Correct | 22 ms | 2176 KB | Output is correct |
35 | Correct | 16 ms | 2048 KB | Output is correct |
36 | Correct | 0 ms | 384 KB | Output is correct |
37 | Correct | 15 ms | 2048 KB | Output is correct |
38 | Correct | 15 ms | 2176 KB | Output is correct |
39 | Correct | 35 ms | 3960 KB | Output is correct |
40 | Correct | 35 ms | 4088 KB | Output is correct |
41 | Correct | 71 ms | 7672 KB | Output is correct |
42 | Correct | 59 ms | 6904 KB | Output is correct |
43 | Correct | 29 ms | 3584 KB | Output is correct |
44 | Correct | 49 ms | 6648 KB | Output is correct |
45 | Correct | 55 ms | 7416 KB | Output is correct |
46 | Correct | 33 ms | 4096 KB | Output is correct |
47 | Correct | 38 ms | 4024 KB | Output is correct |
48 | Correct | 37 ms | 3960 KB | Output is correct |
49 | Correct | 82 ms | 7672 KB | Output is correct |
50 | Correct | 58 ms | 6904 KB | Output is correct |
51 | Correct | 44 ms | 5240 KB | Output is correct |
52 | Correct | 59 ms | 7032 KB | Output is correct |
53 | Correct | 50 ms | 7032 KB | Output is correct |
54 | Correct | 59 ms | 7800 KB | Output is correct |
55 | Correct | 63 ms | 7800 KB | Output is correct |