Submission #584062

#TimeUsernameProblemLanguageResultExecution timeMemory
584062KanaifuGlobal Warming (CEOI18_glo)C++17
100 / 100
53 ms4308 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second int arr[200001]; int n, x; vector <int> sup; int dp[200001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin>>n>>x; for (int i=0; i<n; i++) { cin>>arr[i]; } for (int i=0; i<n; i++) { auto it = lower_bound(sup.begin(), sup.end(), arr[i]); if (it == sup.end()) { sup.pb(arr[i]); dp[i] = sup.size(); continue; } int pos = it - sup.begin(); dp[i] = pos + 1; sup[pos] = arr[i]; } sup.clear(); int mx = 0; for (int i=n-1; i>=0; i--) { auto it = lower_bound(sup.begin(), sup.end(), -(arr[i]-x)); int val = (it-sup.begin()); val += dp[i]; mx = max(val, mx); it = lower_bound(sup.begin(), sup.end(), -(arr[i])); if (it == sup.end()) { sup.pb(-arr[i]); continue; } int pos = it - sup.begin(); sup[pos] = -arr[i]; } cout<<mx; }
#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...