Submission #159810

#	Time	Username	Problem	Language	Result	Execution time	Memory
159810		DS007	Global Warming (CEOI18_glo)	C++17	0 / 100	80 ms	5496 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];
    memset(len, 0, sizeof(len));
    int temp = 0;

    for (int i = 0; i < n; i++) {
        auto it = upper_bound(lis1, lis1 + n + 1, t[i]);
        *it = t[i];
        len[i] = max(temp, (int)(it - lis1));
        temp = max(temp, len[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, t[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;
}

// https://oj.uz/problem/view/CEOI18_glo

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