knucles.cpp

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define what_is(a) cout << #a << " is " << a << "\n"
#define checker(a) cout << "checker reached " << a << "\n"

inline void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}


int t[4*100001];
vector<int> b(100000);

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2] , t[v*2+1]);
    }
}

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

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

void solve(){
    int n,h;
    cin >> n >> h;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin(),b.begin()+n);
    int arr[n];
    memset(arr,0,sizeof(a));
    build(arr,1,0,n-1);
    update(1,0,n-1,lower_bound(b.begin(),b.begin()+n,a[0])-b.begin(),1); 
    for(int i=1;i<n;i++){
        int MAX = 0,pos;
        int temp =0 ;
        pos = lower_bound(b.begin(),b.begin()+n,a[i]-h)-b.begin();
        if(abs(b[pos]-a[i])<h)pos--;
        if(pos>=0&&pos<n)
            MAX = max(MAX, max(1,0,n-1,0,pos)),temp++;;
        pos = lower_bound(b.begin(),b.begin()+n,a[i]+h)-b.begin();
        if(pos>=0&&pos<n)
            MAX = max(MAX, max(1,0,n-1,pos,n-1)),temp++;
        pos = lower_bound(b.begin(),b.begin()+n,a[i])-b.begin();
        update(1,0,n-1,pos,max(1LL,MAX+(MAX!=0))); 
    }
    int ans = max(1,0,n-1,0,n-1);
    cout << ans << "\n";
}

signed main(){
    io();
    solve();
}