Submission #1214944

#TimeUsernameProblemLanguageResultExecution timeMemory
1214944mariamp1Global Warming (CEOI18_glo)C++20
100 / 100
72 ms2736 KiB
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e9 + 7;
int main(){
    int n, x; cin >> n >> x;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 0;
    vector<int> dp(n+1, INF);
    vector<int> pref(n+1);
    for(int i = 1; i <= n; i++){
        int len = lower_bound(dp.begin() + 1, dp.end(), a[i] - x) - dp.begin();
        dp[len] = a[i] - x;
        pref[i] = len;
        ans = max(ans, len);
    }
    for(int i = 0; i <= n; i++){
        dp[i] = INF;
    }
    reverse(a.begin() + 1, a.end());
    for(int i = 1; i <= n; i++){
        int len = lower_bound(dp.begin() + 1, dp.end(), -(a[i] - x)) - dp.begin();
        int idx = n - i +1;
        ans = max(ans, pref[idx] + len - 1);
        len = lower_bound(dp.begin() + 1, dp.end(), -a[i]) - dp.begin();
        dp[len] = -a[i];
    }
    cout << ans << endl;
    return 0;
}
#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...