Submission #159929

#	Time	Username	Problem	Language	Result	Execution time	Memory
159929		DS007	Global Warming (CEOI18_glo)	C++14	62 / 100	89 ms	5884 KiB

glo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, x;
    cin >> n >> x;

    int t[n];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int lis1[n + 1];
    fill(lis1, lis1 + n + 1, 2e9);
    lis1[0] = -1;

    int len[n], val[n];
    memset(len, 0, sizeof(len));
    int temp = 0, temp1 = -1;

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis1, lis1 + n + 1, t[i]);
        *it = t[i];

        if (temp > (int)(it - lis1))
            len[i] = temp, val[i] = temp1;
        else if (temp <= (int)(it - lis1))
            len[i] = temp = (int)(it - lis1), val[i] = temp1 = t[i];
    }

    int lis2[n + 1];
    fill(lis2, lis2 + n + 1, -2e9);
    lis2[n] = 2e9;

    int ans = 0;

    for (int i = n - 1; i >= 0; i--) {
        auto it = upper_bound(lis2, lis2 + n + 1, val[i] - x);
        ans = max(ans, len[i] + n - (int)(it - lis2));
        it = upper_bound(lis2, lis2 + n + 1, t[i]);
        lis2[--it - lis2] = t[i];
    }

    cout << ans;
}

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