Submission #1343530

#TimeUsernameProblemLanguageResultExecution timeMemory
1343530nobasistakenGlobal Warming (CEOI18_glo)C++20
100 / 100
48 ms4680 KiB
#ifdef LOCAL
#include <C:\Users\onlin\Desktop\competitive_programming\codes\debug.hpp>
#else
    #define dbg(x) 
    #define dbgl(x) 
    #define dbgvec(v) 
    #define DBG_OF(i, v)
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(v) v.begin(),v.end()
bool testcases=0;
int dx[]={-1,1,-1,1,2,2,-2,-2};
int dy[]={-2,-2,+2,2,-1,1,-1,1};
const int MOD=1e9+7;
const int inf=1e12;
const int ranint=65729178;
const int mynum=21;
const int N=1e6;
const int siz=N+mynum;
const int tsiz=4*siz;
void solve(){
    int n,x;
    cin>>n>>x;
    int v[n+1];
    for(int i=1;i<=n;i++)cin>>v[i];
    int pref[n+1];
    memset(pref,0,sizeof(pref));
    int ans=-1;
    vector<int> lis;
    for(int i=1;i<=n;i++){
        int num=v[i]-x;
        auto it=lower_bound(all(lis),num);
        if(it==lis.end()){
            lis.push_back(num);
        }
        else{
            lis[(it-lis.begin())]=num;
        }
        pref[i]=lower_bound(all(lis),num)-lis.begin()+1;
        ans=max(ans,pref[i]);
    }
    // for(int i=1;i<=n;i++){
    //     cout<<pref[i]<<' ';
    // }
    // cout<<endl;
    lis.clear();
    for(int i=n;i>0;i--){
        int position=lower_bound(all(lis),-v[i]+x)-lis.begin();
        int ind=lower_bound(all(lis),-v[i])-lis.begin();
        if(lis.size()<=ind){
            lis.push_back(-v[i]);
        }
        else{
            lis[ind]=-v[i];
        }
        ans=max(ans,pref[i]+position);
        //cout<<pref[i]<<' '<<position<<endl;
    }
    cout<<ans<<endl;
}
signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1; 
    if(testcases)cin>>t;
    while(t--){
        solve();
    }
}
#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...