Submission #1271825

#TimeUsernameProblemLanguageResultExecution timeMemory
1271825osmiyumGlobal Warming (CEOI18_glo)C++20
0 / 100
156 ms15988 KiB
#include <bits/stdc++.h>
using namespace std;

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

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

    // LIS soldan sağa
    vector<int> L(n), R(n);
    {
        vector<long long> lis;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(lis.begin(), lis.end(), t[i]);
            if (it == lis.end()) lis.push_back(t[i]);
            else *it = t[i];
            L[i] = lis.size();
        }
    }
    // LIS sağdan sola
    {
        vector<long long> lis;
        for (int i = n - 1; i >= 0; i--) {
            auto it = lower_bound(lis.begin(), lis.end(), -t[i]);
            if (it == lis.end()) lis.push_back(-t[i]);
            else *it = -t[i];
            R[i] = lis.size();
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, L[i]); // normal LIS

    // köprüleme denemesi
    // i < j olacak şekilde
    // t[i] + x < t[j] veya t[i] < t[j] - x ise birleşebilir
    // bunun için t[j] değerine göre max R[j] sakla
    map<long long,int> best;
    for (int j = 0; j < n; j++) {
        if (!best.count(t[j])) best[t[j]] = R[j];
        else best[t[j]] = max(best[t[j]], R[j]);
    }

    // prefix taraması
    int maxL = 0;
    for (int i = 0; i < n; i++) {
        maxL = max(maxL, L[i]);
        // t[i] + x < t[j] için
        auto it = best.upper_bound(t[i] + x);
        if (it != best.end()) {
            ans = max(ans, maxL + it->second);
        }
    }

    cout << ans << "\n";
}
#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...