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 .

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()

def segfunc(x, y):
    return max(x, y)

ide_ele = 0

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    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

size = 10**5*3+10
seg = SegTree([0]*size, segfunc, ide_ele)
for _ in range(N):
    a = int(input())
    maxi = seg.query(max(0, a-K), min(size, a+K+1))
    seg.update(a, maxi+1)
print(seg.query(0, size))

Solution (Python):

import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


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)


def main():
    n, k = input_int_list()
    segtree = SegTree(500000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(500000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()

Solution (Python):
N,K=map(int, input().split())


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        
        return res



dp=[0]*(3*10**5+1)
seg=SegmentTree(dp, max, 0)
length=len(dp)
for i in range(N):
    a=int(input())
    if i==0:
        seg.update(a,1)
    else:
        left=max(0, a-K)
        right=min(length, a+K+1)
        now=seg.query(left, right)
        seg.update(a, now+1)

print(seg.query(0,length))

Solution (Python):
tmpn,k=map(int,input().split())
a=[int(input()) for _ in range(tmpn)]
n=3*10**5+1

def init_max(init_max_val):
    
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


ide_ele_max = 0


num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max([0]*n)

for aa in a:
    maxlen=query_max(max(0,aa-k),min(aa+k,n-1)+1)
    update_max(aa,maxlen+1)

print(query_max(0,n+1))

Solution (Python):









def segfunc(x, y):
    return max(x, y)

 

ide_ele = -1

 
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        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())
tree = [0 for _ in range(400000)]
tree = SegTree(tree, segfunc, ide_ele)
for k in range(N):
  A = int(input())
  n = tree.query(max(0, A-K), min(400000, A+K+1))
  tree.update(A, n+1)
print(tree.query(0, 400000))

Solution (Python):
class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        
        q, self._lazy[idx] = self._lazy[idx], 0

        if q:
            self._lazy[2 * idx] = max(self._lazy[2 * idx],q)
            self._lazy[2 * idx + 1] = max(self._lazy[2 * idx + 1],q)
            self.data[2 * idx] = max(self.data[2 * idx], q)
            self.data[2 * idx + 1] = max(self.data[2 * idx + 1], q)

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = max(self.data[idx], self._func(self.data[2 * idx], self.data[2 * idx + 1]))
            self._push(idx)
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            
            if start & 1:
                self._lazy[start] = max(self._lazy[start], value)
                self.data[start] = max(self.data[start],value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = max(self._lazy[stop], value)
                self.data[stop] = max(self.data[stop],value)
            start >>= 1
            stop >>= 1

        
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
seg = LazySegmentTree([0] * (1 << 20))
for _ in range(n):
    v = int(input())
    most = seg.query(v, v+1)
    
    seg.add(max(0,v - k), v + k + 1, most + 1)
    
print(seg.query(0, 1 << 20))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    class SegmentTree:
        
        
        
        def __init__(self, size, f=lambda x,y : max(x,y), default=0):
            self.size = 2**(size-1).bit_length() 
            self.default = default
            self.dat = [default]*(self.size*2) 
            self.f = f
    
        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])
    
        def query(self, l, r):
            l += self.size
            r += self.size
            lres, rres = self.default, self.default
            while l < r:
                if l & 1:
                    lres = self.f(lres, self.dat[l])
                    l += 1
    
                if r & 1:
                    r -= 1
                    rres = self.f(self.dat[r], rres) 
                l >>= 1
                r >>= 1
            res = self.f(lres, rres)
            return res
    n,k=MI()
    seg=SegmentTree(size=2*300000+1)
    for i in range(n):
        x=I()
        mx=seg.query(300000+x-k,300000+x+k+1)
        
        seg.update(300000+x,mx+1)
    print(seg.query(0,2*300000+2))
        
    
    
    
    








if __name__=="__main__":
    main()

Solution (Python):
import sys



def input():
    return sys.stdin.readline().rstrip()



class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        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


def main():

    ide_ele =0

    def segfunc(x, y):
        return max(x, y)

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

    a = [0]*300002
    seg = SegTree(a,segfunc,ide_ele)

    for i in range(N):
        number =int(input())
        mma = seg.query(max(0,number-K), min(300001, number+K)+1)
        seg.update(number,mma+1)


    print(seg.query(0,300002))












if __name__ == "__main__":
    main()

Solution (Python):
N,k=map(int,input().split())
n=3*10**5+10

def segfunc(x,y):
    return max(x,y)

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele = 0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


for i in range(N):
  x=int(input())
  update(x,query(max(0,x-k),min(n,x+k+1))+1)
print(seg[0])

Solution (Python):

n,k = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))
a.reverse()

dp = [0 for i in range(n)]

def segfunc(x,y):
    return max(x,y)

def init(init_val):
    
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

max_a = 300020

ide_ele = 0
num =2**(max_a-1).bit_length()
seg=[ide_ele]*(2*num - 1)

dp[0] = 1
update(a[0], 1)
for i in range(1,n):
    
    dp[i] = query(max(a[i]-k, 0), min(max_a, a[i]+k+1)) + 1
    update(a[i], dp[i])
print(max(dp))

Solution (Python):
def segfunc(x, y):
    return max(x,y)
n,k = map(int,input().split())
ide_ele = 0
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

A = []

for _ in range(n):
    A.append(int(input()))
B = [0]*300010
seg = SegTree(B,segfunc,ide_ele)
for a in A:
    tmp = seg.query(max(a-k,0),min(a+k,300000)+1)
    seg.update(a,tmp+1)
print(seg.query(0,300001))

Solution (Python):
class SegmentTree:
  def __init__(self, size, default, op = max):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

n,k = map(int,input().split())
a = []
for i in range(n):
  a.append(int(input()))
mxa = max(a)
s = SegmentTree(mxa+1,0)
for i in range(n):
  x = s.get(max(0,a[i]-k),min(mxa,a[i]+k)+1)
  s.update(a[i],x+1)
print(s.get(0,mxa+1))

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate
N,K = map(int,input().split())
A = [int(input()) for i in range(N)]

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self, i=None):
        if i is None:
            return self.data[self.l:self.l + self.N]
        else:
            return self.data[self.l+i]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i, j = i//2, j//2
        return s

M = 300000

seg = SegmentTree([0]*(M+1), max, 0)
for a in A:
    l = max(a-K,0)
    r = min(a+K+1, M+1)
    m = seg.get(l,r)
    seg.set(a, m+1)

print(seg.get(0,M))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353






def segfunc(x, y):
    return max(x, y)


ide_ele = 0

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 = getNM()
A = getArray(N)
ma = max(A)











seg = SegTree([0] * (ma + 1), segfunc, ide_ele)
dp = [1] * N
for i in range(N):
    dp[i] = seg.query(max(0, A[i] - K), min(ma, A[i] + K) + 1) + 1
    seg.update(A[i], dp[i])
print(max(dp))

Solution (Python):

def update(k, x):
    k += T0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

def query(l, r):
    L = l + T0; R = r + T0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

N,K=map(int,input().split())
A=[0]*N
for i in range(N):
    A[i]=int(input())

T=max(A)
T0=2**(T.bit_length())
data=[0]*(2*T0)

DP=[0]*N
for i in range(N-1,-1,-1):
    X=query(max(A[i]-K,0),min(A[i]+K,T)+1)
    DP[i]=X+1
    update(A[i],X+1)

print(max(DP))

Solution (Python):
class segment_tree():
    def __init__(self, N, function, b):
        
        self.n = N
        self.K = (N-1).bit_length()
        self.f = function
        self.b = b
        self.data = [b]*(1+ (1 << (self.K+1)))
        for i in range((1 << self.K)-1, 0, -1):
            self.data[i] = self.f(self.data[i << 1], self.data[i << 1 | 1])

    def update(self, k, value):
        
        k += 1 << self.K
        self.data[k] = value
        while k:
            k = k >> 1
            self.data[k] = self.f(self.data[k << 1], self.data[(k << 1) | 1])

    def query(self, L, R):
        
        L += 1 << self.K
        R += 1 << self.K
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.data[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
ans = 0
seg_tree = segment_tree(6*10**5+10, max, 0)
for i, v in enumerate(A):
    v+= 1
    ans = max(seg_tree.query(max(1, v-K), v+K+1) + 1, 1)
    seg_tree.update(v, ans)
ans = seg_tree.query(0,6*10**5+10)
print(ans)

Solution (Python):
class SegTree:
    
    __slots__ = ["n", "data", "f", "id"]
    
    def __init__(self, li, func, identity):
        self.n = len(li)
        self.f = func
        self.id = identity
        self.data = [self.id]*self.n + li
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def get(self, i):
        return self.data[i+self.n]
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = self.id
        while l < r:
            if l % 2:
                res = self.f(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = self.f(res, self.data[r])
            l //= 2
            r //= 2
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (left_li + right_li[::-1]):
            if not check(self.f(temp, self.data[idx])):
                temp = self.f(temp, self.data[idx])
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(temp, self.data[2*idx])):
                idx = 2*idx
            else:
                temp = self.f(temp, self.data[2*idx])
                idx = 2*idx+1
        return idx - self.n
    
    def min_left(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (right_li + left_li[::-1]):
            if not check(self.f(self.data[idx], temp)):
                temp = self.f(self.data[idx], temp)
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(self.data[2*idx+1], temp)):
                idx = 2*idx+1
            else:
                temp = self.f(temp, self.data[2*idx+1], temp)
                idx = 2*idx
        return idx - self.n

import sys
input = sys.stdin.readline
U = 3*10**5+1
n, k = map(int, input().split())
A = [int(input()) for _ in range(n)]
seg = SegTree([0]*U, max, -1)
for i, a in enumerate(A):
  t = seg.fold(max(0, a-k), min(a+k+1, U))
  seg.update(a, t+1)
ans = seg.fold(0, U)
print(ans)

Solution (Python):
import sys


class SegmentTree:
    """
    https://qiita.com/dn6049949/items/afa12d5d079f518de368 から拝借しています。
    """

    def __init__(self, size, f=lambda x, y: max(x, y), default=0):
        self.size = 2 ** (size - 1).bit_length()
        self.default = default
        self.dat = [default] * (self.size * 2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


input = sys.stdin.buffer.readline

N, K = map(int, input().split())
MAX = 300010
B = SegmentTree(MAX)
for _ in range(N):
    a = int(input()) + 1
    m = B.query(max(1, a - K), min(MAX, a + K + 1))
    B.update(a, m + 1)
print(B.query(1, MAX))