Submission #1332112

#TimeUsernameProblemLanguageResultExecution timeMemory
1332112kutomei3Global Warming (CEOI18_glo)C++20
100 / 100
53 ms4680 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    int arr[n];
    for (auto& p : arr) cin >> p;

    int liss[n];
    vector<int> cur;
    for (int i = 0; i < n; i++) {
        auto lwb = lower_bound(cur.begin(), cur.end(), arr[i] - k);
        liss[i] = (lwb == cur.end() ? cur.size() : lwb - cur.begin()) + 1;
        if (lwb == cur.end()) cur.push_back(arr[i] - k);
        else *lwb = arr[i] - k;
        // for (auto& p : cur) cout << p << ' ';
        // cout << '\n';
        // cout << lwb - cur.begin() << ' ' << '\n';
    }

    //for (auto& p : liss) cout << p << ' ';
    cur.clear();

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        auto lwb = lower_bound(cur.begin(), cur.end(), -arr[i]);
        auto s = lower_bound(cur.begin(), cur.end(), -arr[i] + k);
        int p = (s == cur.end() ? cur.size() : s - cur.begin());
        if (lwb == cur.end()) cur.push_back(-arr[i]);
        else *lwb = -arr[i];
        //cout << i << ' ' << liss[i] << ' ' << p << '\n';
        ans = max(ans, liss[i] + p);
    }

    cout << ans;

    return 0;
}

/*
ct = max(arr[i] - k) + 1
    va < j

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