Submission #550155

#	Time	Username	Problem	Language	Result	Execution time	Memory
550155		Alexandruabcde	Global Warming (CEOI18_glo)	C++14	48 / 100	21 ms	2408 KiB

glo

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 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;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25