Language: C


/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"


template <typename E>
class SegmentTree {
  private:
    vector<E> tree;
    E neutral;
    function<E (E, E)> cumul;

    int treeDataOffset;
    const int ROOT = 1;

    inline int leftChild(const int treeIdx) {
        return  treeIdx * 2;
    }
    inline int rightChild(const int treeIdx) {
        return treeIdx * 2 + 1;
    }
    inline int parent(const int treeIdx) {
        return treeIdx / 2;
    }
    inline bool isOdd(const int idx) {
        return (idx & 0x1);
    }

  public:
    /** @param beg, end The initial data.
     * @param pNeutral the Element neutral to cumul, ie 0 for sum, 1 for product etc
     * @param pCumul The cumulative function to create the "sum" of two nodes.
    **/
    template<typename Iterator>
    SegmentTree(Iterator beg, Iterator end, E pNeutral, function<E (E, E)> pCumul) {
        neutral=pNeutral;
        cumul=pCumul;
        treeDataOffset=end-beg;
        tree=vector<E>(treeDataOffset*2, pNeutral);

        int i=treeDataOffset;
        for (auto it=beg; it!=end; it++)
            tree[i++] = *it;

        for (int j=treeDataOffset - 1; j>=1; j--)
            tree[j] = cumul(tree[leftChild(j)], tree[rightChild(j)]);
    }

    /** Updates all elements in interval(idxL, idxR].
    * iE add 42 to all elements from 4 to inclusive 7:
    * update(4, 8, [](int i1) { return i1+42; });
    */
    void updateRange(int pIdxL, int pIdxR, function<E (E)> apply) {
        pIdxL+=treeDataOffset;
        pIdxR+=treeDataOffset;
        for(int i=pIdxL; i<pIdxR; i++)
            tree[i]=apply(tree[i]);

        while (pIdxL != ROOT) {
            pIdxL=parent(pIdxL);
            pIdxR=max(pIdxL, parent(pIdxR-1));
            for(int i=pIdxL; i<=pIdxR; i++)
                tree[i]=cumul(tree[leftChild(i)], tree[rightChild(i)]);
        }
    }

    /** Updates the data at dataIdx to value returned by apply. */
    void updateApply(int dataIdx, function<E(E)> apply) {
        updateSet(dataIdx, apply(get(dataIdx)));
    }

    /** Updates the data at dataIdx by setting it to value. */
    void updateSet(int dataIdx, E value) {
        int treeIdx = treeDataOffset + dataIdx;
        tree[treeIdx] = value;

        while (treeIdx != ROOT) {
            treeIdx = parent(treeIdx);
            tree[treeIdx] = cumul(tree[leftChild(treeIdx)], tree[rightChild(treeIdx)]);
        }
    }

    /** @return value at single position, O(1) */
    E get(int idx) {
        return tree[idx+treeDataOffset];
    }

    /** @return the cumul(idxL, idxR], iE idxL inclusive, idxR exclusive. */
    E get(int pIdxL, int pIdxR) {
        int idxL = pIdxL + treeDataOffset;
        int idxR = pIdxR + treeDataOffset;
        E cum = neutral;
        while (idxL < idxR) {
            if (isOdd(idxL)) { // left is odd
                cum = cumul(cum, tree[idxL]);
                idxL++;
            }
            if (isOdd(idxR)) {
                idxR--;
                cum = cumul(cum, tree[idxR]);
            }
            idxL = parent(idxL);
            idxR = parent(idxR);
        }
        return cum;
    }

};

/* 
 * dp[j]=max len of a subseq ending in an element j=a[i] (left of current pos)
 **/
const int N=3e5+7;
void solve() {
    cini(n);
    cini(k);

    vi data(N);
    SegmentTree<int> seg(all(data), 0, [](int i1, int i2) { return max(i1,i2); });

    int ans=1;
    for(int i=0; i<n; i++) {
        cini(aux);
        int l=max(0LL, aux-k);
        int r=aux+k+1;
        int prev=seg.get(l,r);
        ans=max(ans, prev+1);
        seg.updateSet(aux, prev+1);
    }
    cout<<ans<<endl;
}

signed main() {
    solve();
}

// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS


Compiler output:
main.c:7:10: fatal error: bits/stdc++.h: No such file or directory
    7 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.