Submission #1364739

#TimeUsernameProblemLanguageResultExecution timeMemory
1364739Godgift42Global Warming (CEOI18_glo)C++20
100 / 100
349 ms23136 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> st1;

void upd1(int v, int tl, int tr, int pos, int val){
    if(tl==tr)st1[v]=max(val,st1[v]);
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)upd1(v*2,tl,tm,pos,val);
        else upd1(v*2+1,tm+1,tr,pos,val);
        st1[v]=max(st1[v*2],st1[2*v+1]);
    }
}

int ma1(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l and tr==r)return st1[v];
    else{
        int tm=(tl+tr)/2;
        return max(ma1(v*2,tl,tm,l,min(r,tm)),ma1(v*2+1,tm+1,tr,max(l,tm+1),r));
    }
}

vector<int> st2;

void upd2(int v, int tl, int tr, int pos, int val){
    if(tl==tr)st2[v]=max(val,st2[v]);
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)upd2(v*2,tl,tm,pos,val);
        else upd2(v*2+1,tm+1,tr,pos,val);
        st2[v]=max(st2[v*2],st2[2*v+1]);
    }
}

int ma2(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l and tr==r)return st2[v];
    else{
        int tm=(tl+tr)/2;
        return max(ma2(v*2,tl,tm,l,min(r,tm)),ma2(v*2+1,tm+1,tr,max(l,tm+1),r));
    }
}

vector<int> st3;

void upd3(int v, int tl, int tr, int pos, int val){
    if(tl==tr)st3[v]=max(val,st3[v]);
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)upd3(v*2,tl,tm,pos,val);
        else upd3(v*2+1,tm+1,tr,pos,val);
        st3[v]=max(st3[v*2],st3[2*v+1]);
    }
}

int ma3(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l and tr==r)return st3[v];
    else{
        int tm=(tl+tr)/2;
        return max(ma3(v*2,tl,tm,l,min(r,tm)),ma3(v*2+1,tm+1,tr,max(l,tm+1),r));
    }
}


int main(){
    int n,k;
    cin >> n>> k;
    vector<int> a(n);
    vector<int> oa(n);
    map<int,int> mp;
    vector<int> val;
    for(int i=0;i<n;i++){
        cin >> a[i];
        oa[i]=a[i];
        mp[a[i]]++;
        if(mp[a[i]]==1)val.push_back(a[i]);
    }
    sort(val.begin(),val.end());
    int cnt=0;
    for(auto& i:mp){
        i.second=cnt;
        cnt++;
    }
    for(int i=0;i<n;i++)a[i]=mp[a[i]];
    vector<int> dp1(n);
    st1.resize(4*cnt);
    for(int i=0;i<n;i++){
        dp1[i]=ma1(1,0,cnt-1,0,a[i]-1)+1;
        upd1(1,0,cnt-1,a[i],dp1[i]);
    }
    vector<int> dp2(n);
    st2.resize(4*cnt);
    for(int i=n-1;i>=0;i--){
        dp2[i]=ma2(1,0,cnt-1,a[i]+1,cnt-1)+1;
        upd2(1,0,cnt-1,a[i],dp2[i]);
    }
    int ans=0;
    st3.resize(4*cnt);
    for(int i=0;i<n;i++){
        int it=lower_bound(val.begin(),val.end(),oa[i]+k)-val.begin();
        it--;
        ans=max(ma3(1,0,cnt-1,0,it)+dp2[i],ans);
        upd3(1,0,cnt-1,a[i],dp1[i]);
    }
    cout << ans << "\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...