제출 #550157

#제출 시각아이디문제언어결과실행 시간메모리
550157AlexandruabcdeGlobal Warming (CEOI18_glo)C++14
100 / 100
53 ms4176 KiB
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;

int N, X;
int val[NMAX];

int dpCresc[NMAX];

int vf;
int Best[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> X;

    for (int i = 1; i <= N; ++ i )
        cin >> val[i];
}

int CautBinar (int value) {
    int st = 1, dr = vf;
    int ans = 0;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Best[mij] < value) {
            ans = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    return ans;
}

int sol = 0;

void Precompute () {
    for (int i = 1; i <= N; ++ i ) {
        int pos = CautBinar(val[i]) + 1;
        dpCresc[i] = pos;

        if (pos > vf) {
            ++ vf;
            Best[vf] = val[i];
        }

        Best[pos] = min(Best[pos], val[i]);
    }

    sol = vf;
}

void Solve () {
    vf = 0;
    for (int i = N; i >= 1; -- i ) {
        int new_ans = CautBinar(-val[i]);
        sol = max(sol, dpCresc[i] + new_ans);

        int new_val = val[i] + X;
        int pos = CautBinar(-new_val) + 1;

        if (pos > vf) {
            ++ vf;
            Best[vf] = -new_val;
        }

        Best[pos] = min(Best[pos], -new_val);
    }

    cout << sol << '\n';
}

int main () {
    Read();
    Precompute();
    Solve();

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