Submission #1308224

#TimeUsernameProblemLanguageResultExecution timeMemory
1308224xnoelGlobal Warming (CEOI18_glo)C++20
100 / 100
95 ms4644 KiB
#include<bits/stdc++.h>
using namespace std;

int main(){
    //freopen("1.in","r",stdin);
    int n,d;
    cin>>n>>d;
    vector<int> v(n);
    for (int i=0;i<n;i++) cin>>v[i];

    vector<int> left(n);
    
    vector<int> dp1;
    for (int i=0;i<n;i++) {
        int x=v[i];
        auto it = lower_bound(dp1.begin(), dp1.end(), x);
        int idx = it - dp1.begin();
        if (it == dp1.end()) {
            dp1.push_back(x);
        } else {
            *it = x;
        }
        left[i]=idx+1;
    }

    vector<int> r_v=v;
    reverse(r_v.begin(),r_v.end());
    for (int i=0;i<n;i++) {r_v[i]*=-1;}
    vector<int> right(n);
    vector<int> dp2;
    for (int i=0;i<n;i++) {
        int x=r_v[i];
        int new_x=x+d;
        
        auto new_it=lower_bound(dp2.begin(), dp2.end(), new_x);
        int new_idx=new_it - dp2.begin();
        right[i]=new_idx+1;


        auto it = lower_bound(dp2.begin(), dp2.end(), x);
        int idx = it - dp2.begin();
        if (it == dp2.end()) {
            dp2.push_back(x);
        } else {
            *it = x;
        }
    }

    reverse(right.begin(),right.end());
    int ans=0;
    for (int i=0;i<n;i++) {
        ans=max(ans,left[i]+right[i]-1);
    }
    cout<<ans<<"\n";
    return 0;
   
}
#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...