Submission #1335794

#TimeUsernameProblemLanguageResultExecution timeMemory
1335794taropolyGlobal Warming (CEOI18_glo)C++20
100 / 100
40 ms2876 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define TEST
const int INF = 2e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n{}, x{};
    cin >> n >> x;
    vector<int> t(n,0);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    vector<int> L(n);
    vector<int> dp{};
    dp.reserve(n+1);
    dp.push_back(-INF);
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(dp.begin(), dp.end(), t[i]) - dp.begin();
        if (pos == dp.size()) {
            dp.push_back(t[i]);
        }
        else {
            dp[pos] = t[i];
        }
        L[i] = pos;
    }


    reverse(t.begin(), t.end());

    dp = vector<int>();
    int ans{0};
    dp.push_back(INF);
    for (int i = 0; i < n; i++) {
        int org_i = n-1-i;
        int r_len = lower_bound(dp.begin(), dp.end(), t[i]-x, greater<int>()) - dp.begin();
        ans = max(ans, L[org_i]+r_len-1);
        int pos = lower_bound(dp.begin(), dp.end(), t[i], greater<int>()) - dp.begin();
        if (pos == dp.size()) {
            dp.push_back(t[i]);
        }else {
            dp[pos] = t[i];
        }

    }
    cout << ans << "\n";
    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...