Submission #1094949

#TimeUsernameProblemLanguageResultExecution timeMemory
1094949ShadowSharkGlobal Warming (CEOI18_glo)C++17
100 / 100
39 ms4452 KiB
#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

*/
#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...