Submission #1094949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094949		ShadowShark	Global Warming (CEOI18_glo)	C++17	100 / 100	39 ms	4452 KiB

glo

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

const int maxN = 2e5 + 5;
int a[maxN], num[maxN];

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

    int n, add;
    cin >> n >> add;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> LIS = {a[1]}; num[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (LIS.back() < a[i]) {
            LIS.push_back(a[i]);
            num[i] = LIS.size();
            continue;
        }

        int x = lower_bound(LIS.begin(), LIS.end(), a[i]) - LIS.begin();
        num[i] = x + 1; LIS[x] = a[i];
    }

    int ans = LIS.size();
    LIS.clear(); LIS.push_back(a[n]);

    for (int i = n - 1; i >= 1; i--) {
        int low = 0, high = LIS.size();
        while (low < high) {
            int mid = (low + high + 1) / 2;

            if (LIS[mid - 1] > a[i] - add) low = mid;
                else high = mid - 1;
        }

        ans = max(ans, num[i] + low);

        if (LIS.back() > a[i]) {
            LIS.push_back(a[i]);
            continue;
        }

        low = 0, high = LIS.size() - 1;
        while (low < high) {
            int mid = (low + high) / 2;

            if (LIS[mid] <= a[i]) high = mid;
                else low = mid + 1;
        }

        LIS[low] = a[i];
    }

    cout << ans;
    return 0;
}

/*
50 15
10 9 8 7 1 3 6 7 1 8 2 2 8 8 2 10 1 10 9 4 9 2 5 6 2 2 4 7 7 4 4 7 7 9 6 5 8 7 7 4 8 9 6 6 10 1 3 2 8 4

*/

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