Submission #1215136

#TimeUsernameProblemLanguageResultExecution timeMemory
1215136takoshanavaGlobal Warming (CEOI18_glo)C++20
100 / 100
92 ms5008 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define fs first #define sc second using namespace std; const int N = 200005, INF = 1e18; int n, x, a[N], pref[N], suf[N]; signed main() { cin >> n >> x; for(int i = 1; i <= n; i++) cin >> a[i]; int ans = 0; int dp[n + 1]; for(int i = 0; i <= n; i++) dp[i] = INF; for(int i = 1; i <= n; i++){ int l = lower_bound(dp + 1, dp + 1 + n, a[i] - x) - dp; dp[l] = a[i] - x; pref[i] = l; ans = max(ans, l); } for(int i = 0; i <= n; i++) dp[i] = INF; reverse(a + 1, a + n + 1); for(int i = 1; i <= n; i++){ int l = lower_bound(dp + 1, dp + 1 + n, -(a[i] - x)) - dp; int id = n - i + 1; ans = max(ans, pref[id] + l - 1); l = lower_bound(dp + 1, dp + n + 1, -a[i]) - dp; dp[l] = -a[i]; } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...