Submission #1280181

#TimeUsernameProblemLanguageResultExecution timeMemory
1280181hanguyendanghuyGlobal Warming (CEOI18_glo)C++20
27 / 100
92 ms9996 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=3e5+5,MAXV=3e5,MOD=1e9+7,INF=3e5+2;
ll n,m,i,j,p,k,ans,dem,st,en,a[MAXN],b[MAXN],x,val[MAXN],c[MAXN];
struct fen{
    ll b[MAXN];
    ll get(ll pos){
        ll ans=0;
        if(pos==0) return 0;
        while(pos>0){
            ans=max(ans,b[pos]);
            pos-=pos&-pos;
        }
        return ans;
    }
    void update(ll pos,ll val){
        while(pos<=INF){
            b[pos]=max(b[pos],val);
            pos+=pos&-pos;
        }
    }
} fensuf,fenpre;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    vector<ll> b;
    for(i=1;i<=n;i++){
        cin>>a[i];
        c[i]=a[i];
        b.pb(a[i]);
    }
    b.pb(0);
    sort(b.begin(),b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for(i=1;i<=n;i++)
        a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin();
    for(i=1;i<=n;i++){
        ll p=fenpre.get(a[i]-1)+1;
        val[i]=p;
        fenpre.update(a[i],p);
    }
    ll ans=0;
    for(i=n;i>=1;i--){
        ll p=fensuf.get(INF-a[i]-1)+1;
        c[i]=lower_bound(b.begin(),b.end(),max(0ll,c[i]-x))-b.begin();
        ans=max(ans,val[i]+fensuf.get(INF-c[i]-1));
        fensuf.update(INF-a[i],p);
    }
    cout<<ans;
}
#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...