제출 #862602

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

using namespace std;

void solve(int l[], int t[], int n) {
    vector<int> v = {t[0]}; l[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (t[i] > v.back()) {
            v.push_back(t[i]);
            l[i] = v.size();
        }
        else {
            int x = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[x] = t[i];
            l[i] = x+1;
        }
    }
}
int x;
void solvee(int r[], int t[], int n) {
    reverse(t, t+n);
    for (int i = 0; i < n; ++i) {
        t[i] = -t[i];
    }
    vector<int> v = {t[0]};
    r[0] = 1;
    for (int i = 1; i < n; ++i) {
        int z = lower_bound(v.begin(), v.end(), t[i] + x) - v.begin();
        r[i] = z + 1;
        if (v.back() < t[i]) {
            v.push_back(t[i]);
        }
        else if (v.back() < t[i]+x) {
            int a = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[a] = t[i];
        }
        else {
            int y = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[y] = t[i];
        }
    }
    reverse(r, r+n);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> x;
    int t[n];
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    int l[n], r[n];
    solve(l, t, n);
    solvee(r, t, n);
    int ans = l[n-1];
    for (int i = 0; i < n; ++i) {
        ans = max(ans, l[i] + r[i] - 1);
    }
    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...