Submission #1105824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105824		Articulation_points	Global Warming (CEOI18_glo)	C++14	100 / 100	43 ms	6776 KiB

glo

/* Dirty code by Articulation_points */
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int oo=2e18+1;
const int MAXN=2e5;
int n,k,a[MAXN+5],dp[MAXN+5],ans;
vector<int>v;
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    v.push_back(oo);
    for(int i=1;i<=n;++i)
        v.push_back(-oo);
    for(int i=n;i>=1;--i){
        int x=lower_bound(v.begin(),v.end(),a[i],greater<int>())-v.begin();
        ans=max(ans,x);
        dp[i]=x;
        v[x]=a[i];
    }
    v.clear();
    v.push_back(-oo);
    for(int i=1;i<=n;++i)
        v.push_back(oo);
    for(int i=1;i<=n;++i){
        int x=lower_bound(v.begin(),v.end(),a[i]+k)-v.begin();
        ans=max(ans,x+dp[i]-1);
        x=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        v[x]=a[i];
    }
    cout<<ans<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25