Submission #1349725

#TimeUsernameProblemLanguageResultExecution timeMemory
1349725bentonewGlobal Warming (CEOI18_glo)C++20
62 / 100
45 ms11220 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const ll INF = numeric_limits<ll>::max();
const int inf = numeric_limits<int>::max();
const char nl = '\n', sp = ' ';

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

    ll n, x;
    cin >> n >> x;
    vector<ll> arr(n,0);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    vector<pll> LIS(n,{0,0}); //longest IS form [O,i]
    vector<pll> LDS(n,{0,0});
    vector<ll> OPT(n,INF); // optimal of length n
    vector<ll> BACKOPT(n,-INF);

    for(int i = 0; i < n; i++){
        ll value = arr[i];
        auto it = lower_bound(OPT.begin(), OPT.end(), value);
        int index = it - OPT.begin() ;
        OPT[index] = value;



        ll temp = INF;
        auto las = lower_bound(OPT.begin(),OPT.end(),temp);
        las--;
        int lastid = (las - OPT.begin());
        LIS[i] = {lastid + 1,OPT[lastid]};

        //longest increasing from 0 to i, that has the minimum ending element as established already
    }

    for(int i = n-1; i >= 0; i--){
        //find longest decreasing sequence
        ll value = arr[i];
        auto it = lower_bound(BACKOPT.begin(), BACKOPT.end(), value, greater<ll>());
        //find first element LEQ, we want to replace this
        int index = it - BACKOPT.begin() ;
        BACKOPT[index] = value;
        // cout << index << sp << value << endl;
        ll temp = -INF;
        auto las = lower_bound( BACKOPT.begin(),BACKOPT.end(),temp,greater<ll>());
        las--;
        int lastid = (las - BACKOPT.begin());
        
        
        LDS[i] = {lastid + 1, BACKOPT[lastid]}; //longest with lowest last element

        
    }
    // for(int i = 0 ; i < n; i++){
    //     cout << LIS[i].first << sp;
    // }
    // cout << nl;

    // for(int i = 0 ; i < n; i++){
    //     cout << LIS[i].second << sp;
    // }
    // cout << nl << nl;
    // for(int i = 0 ; i < n; i++){
    //     cout << LDS[i].first << sp;
    // }
    // cout << nl;
    // for(int i = 0 ; i < n; i++){
    //     cout << LDS[i].second << sp;
    // }
    // cout << nl;


    ll maxi = -INF;
    for(int i = 0; i < n-1; i++){
        auto [LISLEN, LISVAL] = LIS[i];
        auto [LDSLEN, LDSVAL] = LDS[i+1];
        ll actual_len = LISLEN;
        if(llabs(LISVAL - LDSVAL) < x){
            actual_len += LDSLEN;
        }
        maxi = max(maxi,actual_len);
    }
    maxi = max(maxi, LIS[n-1].first);
    cout << maxi << nl;



}



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