# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
310941 | 2020-10-08T17:26:14 Z | Falcon | Global Warming (CEOI18_glo) | C++17 | 131 ms | 9432 KB |
#pragma GCC optimize("O2") #include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d)) #define pb push_back #ifdef DEBUG #define debug(x...) { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); } #define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0; } #else #define debug(x...) 42 #define light_debug(x) 42 #endif template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } using ll = long long; using pii = pair<int, int>; using vi = vector<int>; template<typename IT, typename T> vi lis_ending_at(IT s, IT e, const T& comp) { int n{e - s}; vi v, dp(n); rep(i, n) { int x = *(s + i); auto it = lower_bound(all(v), x, comp); dp[i] = it - v.begin() + 1; if(it == v.end()) v.pb(x); else *it = x; } return dp; } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); #ifdef DEBUG freopen("debug", "w", stderr); #endif int n, x; cin >> n >> x; vi a(n); rep(i, n) cin >> a[i]; vi end_at{lis_ending_at(all(a), less<int>())}; vi start_at{lis_ending_at(rall(a), greater<int>())}; reverse(all(start_at)); debug(start_at, end_at); map<int, int> mp; mp[INT_MAX] = 0; vi tmp; int ans{0}; rep3(i, n - 1, 0, -1) { auto it = mp.upper_bound(a[i]); ckmax(ans, end_at[i] + it->second); it = mp.upper_bound(a[i] + x); if(it != mp.end() && it->second >= start_at[i]) continue; while(it != mp.begin()) { --it; if(it->second <= start_at[i]) tmp.pb(it->first); else break; } for(auto v : tmp) mp.erase(v); tmp.clear(); mp[a[i] + x] = start_at[i]; } cout << ans << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() << "ms\n"; #endif return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 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 | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 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 | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 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 | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 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 | 416 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 | 125 ms | 4600 KB | Output is correct |
2 | Correct | 128 ms | 4600 KB | Output is correct |
3 | Correct | 128 ms | 4792 KB | Output is correct |
4 | Correct | 124 ms | 4600 KB | Output is correct |
5 | Correct | 121 ms | 8540 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 1408 KB | Output is correct |
2 | Correct | 29 ms | 1408 KB | Output is correct |
3 | Correct | 30 ms | 1408 KB | Output is correct |
4 | Correct | 25 ms | 2356 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 24 ms | 2348 KB | Output is correct |
7 | Correct | 24 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 2544 KB | Output is correct |
2 | Correct | 56 ms | 2552 KB | Output is correct |
3 | Correct | 120 ms | 4600 KB | Output is correct |
4 | Correct | 120 ms | 8672 KB | Output is correct |
5 | Correct | 53 ms | 4456 KB | Output is correct |
6 | Correct | 75 ms | 8196 KB | Output is correct |
7 | Correct | 102 ms | 9000 KB | Output is correct |
8 | Correct | 45 ms | 2560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 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 | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 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 | 416 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 | 125 ms | 4600 KB | Output is correct |
28 | Correct | 128 ms | 4600 KB | Output is correct |
29 | Correct | 128 ms | 4792 KB | Output is correct |
30 | Correct | 124 ms | 4600 KB | Output is correct |
31 | Correct | 121 ms | 8540 KB | Output is correct |
32 | Correct | 32 ms | 1408 KB | Output is correct |
33 | Correct | 29 ms | 1408 KB | Output is correct |
34 | Correct | 30 ms | 1408 KB | Output is correct |
35 | Correct | 25 ms | 2356 KB | Output is correct |
36 | Correct | 1 ms | 384 KB | Output is correct |
37 | Correct | 24 ms | 2348 KB | Output is correct |
38 | Correct | 24 ms | 1408 KB | Output is correct |
39 | Correct | 55 ms | 2544 KB | Output is correct |
40 | Correct | 56 ms | 2552 KB | Output is correct |
41 | Correct | 120 ms | 4600 KB | Output is correct |
42 | Correct | 120 ms | 8672 KB | Output is correct |
43 | Correct | 53 ms | 4456 KB | Output is correct |
44 | Correct | 75 ms | 8196 KB | Output is correct |
45 | Correct | 102 ms | 9000 KB | Output is correct |
46 | Correct | 45 ms | 2560 KB | Output is correct |
47 | Correct | 61 ms | 2552 KB | Output is correct |
48 | Correct | 60 ms | 2552 KB | Output is correct |
49 | Correct | 131 ms | 4728 KB | Output is correct |
50 | Correct | 120 ms | 8664 KB | Output is correct |
51 | Correct | 87 ms | 7748 KB | Output is correct |
52 | Correct | 116 ms | 8664 KB | Output is correct |
53 | Correct | 81 ms | 8668 KB | Output is correct |
54 | Correct | 109 ms | 9432 KB | Output is correct |
55 | Correct | 97 ms | 4728 KB | Output is correct |