Submission #1084121

#TimeUsernameProblemLanguageResultExecution timeMemory
1084121ZeroCoolGlobal Warming (CEOI18_glo)C++14
100 / 100
88 ms6996 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define ar array const int LOG = 20; const int MOD = 1e9 + 7; const int INF = 1e18; const int N = 2e5 + 20; int A[N]; int pref[N]; signed main() { int n,x; cin>>n>>x; for (int i = 0; i < n; i++)cin >> A[i]; int dp[n]; for(int i = 0;i < n;i++)dp[i] = INF; int ans = 0; for (int i = 0; i < n; i++) { int j = lower_bound(dp, dp + n, A[i]) - dp; dp[j] = A[i]; pref[i] = j + 1; ans = max(ans, pref[i]); } for(int i = 0;i < n;i++)dp[i] = INF; for (int i = n - 1; i >= 0; i--) { int j = lower_bound(dp, dp + n, -A[i] + x) - dp; ans = max(ans, pref[i] + j); int k =lower_bound(dp, dp + n, -A[i]) - dp; dp[k] = -A[i]; } cout<<ans; }
#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...