Submission #1271828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271828		osmiyum	Global Warming (CEOI18_glo)	C++20	0 / 100	77 ms	18456 KiB

glo

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

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

    int n; ll x;
    if(!(cin>>n>>x)) return 0;
    vector<ll> t(n);
    for(int i=0;i<n;i++) cin>>t[i];

    // Helper lambda to compute prefix LIS info when values are transformed by a function f(i)
    auto compute_prefix = [&](auto transform){
        vector<int> len(n);
        vector<ll> tail(n);
        vector<ll> tails; // patience tails
        for(int i=0;i<n;i++){
            ll v = transform(t[i]);
            auto it = lower_bound(tails.begin(), tails.end(), v);
            if(it==tails.end()) tails.push_back(v);
            else *it = v;
            len[i] = (int)tails.size();
            tail[i] = tails.back(); // minimal possible tail for the current maximal length
        }
        return tuple<vector<int>, vector<ll>>(len, tail);
    };

    // Helper lambda to compute suffix LIS info when values are transformed by a function f(i)
    // We process from right to left; the recorded "first" value for suffix starting at i
    // corresponds to the tail value in the reversed processing (see explanation).
    auto compute_suffix = [&](auto transform){
        vector<int> len(n);
        vector<ll> first(n);
        vector<ll> tails;
        for(int idx=n-1; idx>=0; --idx){
            ll v = transform(t[idx]);
            auto it = lower_bound(tails.begin(), tails.end(), v);
            if(it==tails.end()) tails.push_back(v);
            else *it = v;
            len[idx] = (int)tails.size();
            first[idx] = tails.back(); // minimal possible "first" value for maximal length in suffix
        }
        return tuple<vector<int>, vector<ll>>(len, first);
    };

    // Original LIS (no change) -- prefix info
    auto [pref_len_orig, pref_tail_orig] = compute_prefix([&](ll v){ return v; });
    // Original suffix info (no change) - we might use it as baseline
    auto [suf_len_orig, suf_first_orig] = compute_suffix([&](ll v){ return v; });

    // Prefix when we subtract x from prefix elements
    auto [pref_len_minus, pref_tail_minus] = compute_prefix([&](ll v){ return v - x; });
    // Prefix when we add x to prefix elements
    auto [pref_len_plus, pref_tail_plus] = compute_prefix([&](ll v){ return v + x; });

    // Suffix when we add x to suffix elements
    auto [suf_len_plus, suf_first_plus] = compute_suffix([&](ll v){ return v + x; });
    // Suffix when we subtract x from suffix elements
    auto [suf_len_minus, suf_first_minus] = compute_suffix([&](ll v){ return v - x; });

    // baseline: original LIS (no change)
    int ans = 0;
    if(n>0) ans = pref_len_orig[n-1];

    // Consider taking only a modified prefix or only a modified suffix
    for(int i=0;i<n;i++){
        ans = max(ans, pref_len_minus[i]);
        ans = max(ans, pref_len_plus[i]);
        ans = max(ans, suf_len_plus[i]);
        ans = max(ans, suf_len_minus[i]);
    }

    // Combine prefix (decreased by x) with suffix (increased by x)
    for(int i=0;i+1<n;i++){
        int a = pref_len_minus[i];
        int b = suf_len_plus[i+1];
        ll last_pref = pref_tail_minus[i];
        ll first_suf = suf_first_plus[i+1];
        if(last_pref < first_suf) ans = max(ans, a + b);
    }
    // Combine prefix (increased by x) with suffix (decreased by x)
    for(int i=0;i+1<n;i++){
        int a = pref_len_plus[i];
        int b = suf_len_minus[i+1];
        ll last_pref = pref_tail_plus[i];
        ll first_suf = suf_first_minus[i+1];
        if(last_pref < first_suf) ans = max(ans, a + b);
    }

    cout<<ans<<"\n";
    return 0;
}

• 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