Submission #1271825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271825		osmiyum	Global Warming (CEOI18_glo)	C++20	0 / 100	156 ms	15988 KiB

glo

#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";
}

• 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