Problem:


Score : 400 points

Problem Statement

You are given a sequence A_1, A_2, ..., A_N and an integer K.

Print the maximum possible length of a sequence B that satisfies the following conditions:

B is a (not necessarily continuous) subsequence of A.

For each pair of adjacents elements of B, the absolute difference of the elements is at most K.

Constraints

1 \leq N \leq 300,000

0 \leq A_i \leq 300,000

0 \leq K \leq 300,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1
A_2
:
A_N

Output

Print the answer.

Sample Input 1

10 3
1
5
4
3
8
6
9
7
2
4

Sample Output 1

7

For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.

It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).

All of the absolute differences between two adjacent elements (|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) are at most K = 3.



Sample input:
10 3
1
5
4
3
8
6
9
7
2
4


Sample output:
7

Submission status: Accepted

Solution code:


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)
lim = 4*10**5
n,k = map(int,input().split())
seg = SegTree(lim)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(max(0,a-k),min(lim,a+k+1)) + 1)

print(seg.fold(0,lim))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class SegmentTree(object):
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)
 
	# 区間クエリの種類
	def calc(self, a, b):
		return max(a, b)
 
	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])
 
	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
 
		return m

def main():
    n, k = i_map()
    size = 300000 + 2
    seg = SegmentTree(size)
    for _ in range(n):
        a = i_input()
        l = max(0, a -k)
        r = min(size - 1, a + k)
        res = seg.query(l, r)
        seg.update(a, res + 1)
 
    ans = seg.query(0, size - 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d=[0]*6**8
n,k,*a=map(int,open(0).read().split())
a=d+a
while n:d[n]=max(d[j]for j in range(n,n+99)if abs(a[-n]-a[-j])<=k)+1;n-=1
print(max(d))

Submission status: Accepted

Solution code:
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

###
class SegmentTree:
    """
    セグメント木: 区間の最大値等を効率よく更新する
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])
 
    def add(self, i, x):
        self.update(i, self.get(i) + x)
 
    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s
 
    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]
 
    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]
 
    def bisearch_fore(self, l, r, x, func):
        """ 区間[l,r]で左から最初にxに対して比較の条件を満たすような値が出現する位置 """
 
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if func(self.query(l, mid+1), x):
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF
 
    def bisearch_back(self, l, r, x, func):
        """ 区間[l,r]で右から最初にxに対して比較の条件を満たすような値が出現する位置 """
 
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if func(self.query(mid, r+1), x):
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF
 
    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()
###


N,K = LI()
A = [I() for _ in range(N)]
ans = 0

M = max(A)
seg = SegmentTree(M+1, max, -INF, [0]*(M+1))
 
for a in A:
    start = max(0, a - K)
    end = min(M, a + K) + 1
    res = seg.query(start, min(a+K, M)+1)
    # 区間の最大値をインクリメント
    res += 1
    seg.update(a, res)
ans = seg.all()
print(ans)


# t = [0]*300001

# for a in A:
#     start = max(0, a - K)
#     end = min(N + 1, a + K+1)
#     t[a]=max(t[start:end])+1

# ans = max(t)

# # ビット全探索
# for i in range(1 << N):
#     c = 0
#     flag = True
#     before = -1
#     for j in range(N):
#         if (i >> j) & 1 == 0:
#             continue
#         if not (before == -1) and abs(before - A[j])>K:
#             flag = False
#             break
#         before = A[j]
#         c += 1
#     # 全てX以上であれば更新
#     if flag:
#         ans = max(ans, c)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class SegmentTree(object):
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)
 
	# 区間クエリの種類
	def calc(self, a, b):
		return max(a, b)
 
	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])
 
	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
 
		return m

def main():
	N, K = i_map()
	n = 3 * (10 ** 5) + 2
	Seg = SegmentTree(n)
	for _ in range(N):
		a = int(input())
		l = max(0, a - K)
		r = min(n - 1, a + K)
		res = Seg.query(l, r)
		Seg.update(a, res + 1)
 
	ans = Seg.query(0, n - 1)
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d=[0]*6**8
n,k,*a=map(int,open(0).read().split()+d)
for i in range(n):d[i]=max(d[j]for j in range(i-99,i+1)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Accepted

Solution code:
# Segment Treeを使う。一点更新，区間最大値

N, K = map(int, input().split())

seglen = 1 << 19

segtree = [0 for _ in range(seglen * 2)]
# segtree[seglen + i] = Bの最後の値に i を使う時のlongest len

def segset(ind, val):
    segtree[ind] = val
    ind //= 2
    while ind != 0:
        segtree[ind] = max(segtree[ind*2], segtree[ind*2 + 1])
        ind //= 2
    return


def segmax(l, r):
    ret = 0

    while l < r:

        if l % 2 == 1:
            ret = max(ret, segtree[l])
            l += 1
        l //= 2

        if r % 2 == 1:
            ret = max(ret, segtree[r - 1])
            r -= 1
        r //= 2

    return ret

A = []
for _ in range(N):
    a = int(input())
    A.append(a)

ans = 0

for a in A:
    a_ind = seglen + a

    l = max(seglen, a_ind - K)
    r = min(seglen + 400000, a_ind + K + 1)

    longest = segmax(l, r)

    segset(a_ind, longest + 1)

    ans = max(ans, longest + 1)

print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[0]*n
for i in range(n):d[i]=max(d[j]for j in range(max(0,i-99),i+1)if abs(a[i]-a[j])<=k)+1
print(max(d))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[1]*n
for i in range(n):d[i]=max([d[i]]+[d[j]+1for j in range(max(0,i-99),i)if abs(a[i]-a[j])<=k])
print(max(d))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[1]*n
for i in range(n):
 for j in range(max(0,i-99),i):d[i]=max(d[i],d[j]*(abs(a[i]-a[j])<=k)+1)
print(max(d))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[1]*n
for i in range(n):
 for j in range(max(0,i-99),i):
  if abs(a[i]-a[j])<=k:d[i]=max(d[i],d[j]+1)
print(max(d))

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
n=7**7
d=[0]*n*2
for a in a:
    l,r=max(0,a-k)+n,a+k-~n
    a+=n
    while l<r:
        if l&1:
            d[a]=max(d[a],d[l]+1)
            l+=1
        if r&1:
            r-=1
            d[a]=max(d[a],d[r]+1)
        l>>=1
        r>>=1
    while a:
        a>>=1
        d[a]=max(d[a+a],d[a-~a])
print(max(d))

Submission status: Accepted

Solution code:
header_code = """
#include "/opt/ac-library/atcoder/internal_bit.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};

}
"""

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/ac-library]
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdio cimport getchar, printf
from libcpp cimport bool
from libcpp.vector cimport vector
from libcpp.string cimport string
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_min:
        segtree_min(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMin:
    cdef segtree_min *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_min(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_max:
        segtree_max(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMax:
    cdef segtree_max *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_max(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)


def SegTree(v, op):
    if op=="min":
        return SegTreeMin(v)
    elif op=="max":
        return SegTreeMax(v)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import SegTree, ReadInt

def smax(a,b):
    return a if a>b else b

def smin(a,b):
    return b if a>b else a

def main():
    N,K = ReadInt(2)
    A = ReadInt(N)
    maxA = max(A)
    ST1 = SegTree([0]*(maxA+1), "max")
    ST2 = SegTree([0]*(maxA+1), "max")
    D1 = [0]*N
    D2 = [0]*N
    for i in range(N):
        a = A[i]
        b = ST1.prod(smax(a-K,0),smin(a+K,maxA)+1)
        c = ST1.get(a)
        if b+1>c:
            ST1.set(a,b+1)
            d = b+1
        else:
            d = c
        D1[i] = d

        a = A[N-i-1]
        b = ST2.prod(smax(a-K,0),smin(a+K,maxA)+1)
        c = ST2.get(a)
        if b+1>c:
            ST2.set(a,b+1)
            d = b+1
        else:
            d = c
        D2[N-i-1] = d

    ans = 0
    for i in range(N):
        ans = smax(D1[i]+D2[i]-1, ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def segfunc(x, y):
    return max(x, y)
ide_ele = -float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
max_v = max(A)
seg = SegTree([0]*max_v, segfunc, ide_ele)

for i in A:
    f = seg.query(max(0,i-K),min(max_v,i+K)+1)
    seg.update(i,f+1)

print(seg.query(0,max_v+1))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys

class SegmentTree():
    def __init__(self,n):
        self.e = 0
        self.r = 0 #ノードの段数
        cnt = 0
        while cnt<n:
            cnt=2**self.r
            self.r +=1
        self.tree = [self.e]*(2**self.r -1)# 0-index
        self.n = 2**(self.r-1) #一番下のnodeの数
    def build(self,lis):
        for i,val in enumerate(lis):
            self.update(i,val)
    def func(self,a,b): #適宜書き換え
        return max(a,b)
    def update(self,i,val):
        i += self.n -1
        self.tree[i] =self.func(self.tree[i],val)
        while i>0:
            i = (i-1)//2
            self.tree[i] = self.func(self.tree[i*2+1],self.tree[i*2+2])
    def query(self,l,r):
        l += self.n -1
        r += self.n -1 #半開区間[l,r) ==[l,r-1]  に対するquery
        lval = self.e
        rval = self.e
        while r>l:
            if l%2 == 0:
                lval = self.func(lval,self.tree[l])
                l+=1
            if r%2==0:
                rval = self.func(rval,self.tree[r-1])
                r-=1
            r//=2
            l//=2
        return self.func(lval,rval)
    def index(self,i):
        return i+self.n -1
    def value(self,i):
        return self.tree[i+self.n -1]

n,k = ma()
LR = []
A=[]
for i in range(n):
    A.append(ni())

mx=max(A)
dp = SegmentTree(mx+1)
for a in A:
    max_len = dp.query(max(0,a-k),min(mx+1,a+k+1))
    dp.update(a,max_len+1)
print(dp.query(0,mx+1))