제출 #1000520

#제출 시각아이디문제언어결과실행 시간메모리
1000520niwradGlobal Warming (CEOI18_glo)C++17
100 / 100
109 ms6260 KiB
#include <bits/stdc++.h>

using namespace std;
int inf = 2e9 + 7;


int main() {
    int n, x;
    cin >> n >> x;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    vector<int> suff_dp(n + 1, -inf);
    suff_dp[0] = inf;
    vector<pair<int, int>> steps(n, {-1, -1});
    for (int i = n - 1; i >= 0; i--) {
        int l = (int) (upper_bound(suff_dp.begin(), suff_dp.end(), vec[i] + x, greater_equal<int>()) - suff_dp.begin());
        if (suff_dp[l] < vec[i] + x) {
            steps[i] = {l, suff_dp[l]};
            suff_dp[l] = vec[i] + x;
        }
    }
    int max = 0;
    for (int i = 0; i <= n; i++) {
        if (suff_dp[i] != -inf) {
            max = i;
        }
    }
    vector<int> pref_dp(n + 1, inf);
    pref_dp[0] = -inf;
    for (int i = 0; i < n; i++) {
        int s = -1;
        if (steps[i].first != -1) {
            s = steps[i].first;
            suff_dp[steps[i].first] = steps[i].second;
        }
        int l = (int) (upper_bound(pref_dp.begin(), pref_dp.end(), vec[i]) - pref_dp.begin());
        if (pref_dp[l - 1] < vec[i] && vec[i] < pref_dp[l]) {
            pref_dp[l] = vec[i];
            int p = (int) (lower_bound(suff_dp.begin(), suff_dp.end(), vec[i], greater<int>()) - suff_dp.begin());
            l += p - 1;
            max = std::max(max, l);
        }
        if (s != -1) {
            int p = (int) (lower_bound(pref_dp.begin(), pref_dp.end(), suff_dp[s]) - pref_dp.begin());
            max = std::max(max, s + p - 1);
        }
    }
    cout << max << "\n";
}


#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...