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
input=sys.stdin.readline

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
 
    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])
 
    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res
 

seg=SegTree([0]*300001,0,max)

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

for i in a:
    l=max(0,i-k)
    r=min(300000,i+k)

    pin=seg.query(l,r+1)+1
    seg.update(i,pin)


print(seg.query(0,300001))

Solution (Python):
import sys
input=sys.stdin.readline

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = [ide_ele]*2*self.num
        
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
 
    def update(self, k, x):
        k += self.num
        self.seg[k] = x
        while k:
            k = k >> 1
            self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])
 
    def query(self, l, r):
        if r <= l:
            return self.ide_ele
        l += self.num
        r += self.num
        res = self.ide_ele
        while l < r:
            if r & 1:
                r -= 1
                res = self.segfunc(res, self.seg[r])
            if l & 1:
                res = self.segfunc(res, self.seg[l])
                l += 1
            l = l >> 1
            r = r >> 1
        return res
 
def func(x, y):
    return max(x,y)

seg=SegTree([0]*300001,0,func)

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

for i in a:
    l=max(0,i-k)
    r=min(300000,i+k)

    pin=seg.query(l,r+1)+1
    seg.update(i,pin)


print(seg.query(0,300001))

Solution (Python):
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        
        
        self.tree = [self.default] * self.size * 2
        self.range = [None] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size):
            self.range[self.size + i] = (i, i+1)
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])
            self.range[i] = (self.range[i*2][0], self.range[i*2+1][1])

    def get(self, index):
        return self.tree[self.size + index]

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    
    def query(self, a, b):
        q = [1]
        ret = self.default
        while len(q):
            k = q.pop()
            l, r = self.range[k]
            if r <= a or b <= l:
                continue
            if a <= l and r <= b:
                ret = self.merge(ret, self.tree[k])
            else:
                q.append(k*2)
                q.append(k*2+1)
        return ret


def main():
    MAX = 300001
    N, K = map(int, input().split())
    rmq = SegmentTree([0]*MAX, merge_func=max, default=0)
    for _ in range(N):
        A = int(input())
        mx = rmq.query(A-K, A+K+1)
        rmq.update(A, mx+1)
    ans = rmq.query(0, MAX)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):



class Segment:
    def __init__(self, N, init_val, segfunc, identity_element):
        """
        segfunc : min, +, *, xor, gcd など
        identity_element : 単位元(min:inf, 和:0, 積:1, xor:0, gcd:0)
        """
        self.segfunc = segfunc
        self.identity_element = identity_element
        self.N0 = 2 ** (N - 1).bit_length()
        
        self.dat = [self.identity_element] * (2 * self.N0)

        
        for i in range(N):
            self.dat[i + self.N0 - 1] = init_val[i]
        
        for i in range(self.N0 - 2, -1, -1):
            self.dat[i] = self.segfunc(self.dat[2 * i + 1], self.dat[2 * i + 2])

    
    def update(self, k, x):
        k += self.N0 - 1
        self.dat[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.dat[k] = self.segfunc(self.dat[2 * k + 1], self.dat[2 * k + 2])

    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.identity_element
        
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.dat[R - 1])
            if L & 1:
                s = self.segfunc(s, self.dat[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s


import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

n, k = map(int, input().split())
seg = Segment(300000, [0] * 300000, max, 0)
ans = 0
for i in range(n):
    a = int(input())
    l = max(a - k, 0)
    r = min(a + k, 300000) + 1
    res = seg.query(l, r) + 1
    ans = max(res, ans)
    seg.update(a, res)

print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


def input():
    return sys.stdin.readline()[:-1]


class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i
        self.arr[k] = x

        while k > 0:
            k >>= 1
            self.arr[k] = self.fn(self.arr[2 * k], self.arr[2 * k + 1])

    def query(self, l, r):
        l += self.n
        r += self.n
        lres, rres = self.unity, self.unity
        while l < r:
            
            if l & 1:
                lres = self.fn(lres, self.arr[l])
                l += 1

            
            if r & 1:
                r -= 1
                rres = self.fn(rres, self.arr[r])

            
            l >>= 1
            r >>= 1

        return self.fn(lres, rres)




    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()


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

st = SegmentTree(MAX + 10, fn=lambda x, y: max(x, y), unity=0)
ans = 0

while N > 0:
    A = int(input())
    minimum, maximum = max(A - K, 0), min(A + K, MAX)
    x = st.query(minimum, maximum + 1) + 1
    ans = max(ans, x)
    st.update(A, x)
    N -= 1

print(ans)

Solution (Python):

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



ide_ele = -float('inf')


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())
a=[ int(input()) for _ in range(n)]
A=[0 for _ in range(303030)]
seg=SegTree(A,segfunc,ide_ele)
for x in a:
  seg.update(x,seg.query(max(0,x-k),min(303030,x+k+1))+1)
  
ans=seg.query(0,303030)
print(ans)

Solution (Python):
from sys import stdin
input = stdin.readline
class LazySegmentTree():
    def __init__(self, n, init, merge_func=min, ide_ele=10 ** 18):
        self.n = (n - 1).bit_length()
        self.merge_func = merge_func
        self.ide_ele = ide_ele
        self.data = [0 for i in range(1 << (self.n + 1))]
        self.lazy = [0 for i in range(1 << (self.n + 1))]
        for i in range(n):
            self.data[2 ** self.n + i] = init[i]
        for i in range(2 ** self.n - 1, 0, -1):
            self.data[i] = self.merge_func(self.data[2 * i], self.data[2 * i + 1])

    def propagate_above(self, i):
        m = i.bit_length() - 1
        for bit in range(m, 0, -1):
            v = i >> bit
            add = self.lazy[v]
            self.lazy[v] = 0
            self.data[2 * v] += add
            self.data[2 * v + 1] += add
            self.lazy[2 * v] += add
            self.lazy[2 * v + 1] += add

    def remerge_above(self, i):
        while i:
            i >>= 1
            self.data[i] = self.merge_func(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]

    def update(self, l, r, x):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        while l < r:
            self.data[l] += x * (l & 1)
            self.lazy[l] += x * (l & 1)
            l += (l & 1)
            self.data[r - 1] += x * (r & 1)
            self.lazy[r - 1] += x * (r & 1)
            l >>= 1
            r >>= 1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self, l, r):
        l += 1 << self.n
        r += 1 << self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res = self.ide_ele
        while l < r:
            if l & 1:
                res = self.merge_func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.merge_func(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
def solve():
    n,k = map(int,input().split())
    a = [int(inp) for inp in stdin.read().splitlines()]
    N = 300010
    cnt = [0]* N
    LST = LazySegmentTree(N,cnt,max,-1)
    res = 0
    for i in a:
        v = LST.query(max(0,i - k),min(N,i+k) + 1)
        res = max(res,v + 1)
        cur = LST.query(i,i+1)
        LST.update(i,i+1,v+1-cur)
    print(res)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy







mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])


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):
        """
        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 = inpm()
A = inplm(n)

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

for a in A:
    seg.update(a,seg.query(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.query(0,300001))

Solution (Python):
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n,k=map(int,input().split())
arr=[int(input()) for _ in range(n)]
lim=max(arr)
st=SegmentTreeMax(lim,0)
for val in arr:
  l=max(0,val-k)
  r=min(lim,val+k)
  tmp=st.query(l,r)
  st.update(val,tmp+1)
print(st.query(0,lim))

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])
    from nbmodule import cc
    cc.compile()
import numpy as np
from numpy import int64
from nbmodule import solve


f = open(0)
N, K = [int(x) for x in f.readline().split()]
A = np.fromstring(f.read(), dtype=int64, sep=' ')
ans = solve(N, K, A)
print(ans)

'''

import numpy as np
from numpy import int64
from numba import njit
from numba.types import i8
from numba.pycc import CC
import nbacl.segtree as seg
cc = CC('nbmodule')


@cc.export('solve', (i8, i8, i8[:]))
@njit
def solve(N, K, A):
    dp = np.zeros(300_001, dtype=int64)
    d = seg.segtree(dp, max, 0)
    for i in range(N):
        x = seg.prod(d, max, (A[i] - K) if A[i] > K else 0, (A[i] + K + 1) if A[i] + K < 300_000 else 300_001) + 1
        seg.set(d, max, A[i], x)
    return seg.all_prod(d)


if __name__ == '__main__':
    cc.compile()

import numpy as np
from numba import njit
from numba.types import i8


@njit
def ceil_pow2(n):
    x = 0
    while (1 << x) < n:
        x += 1
    return x


@njit
def segtree(a, op, e):
    log = ceil_pow2(a.shape[0])
    size = 1 << log
    d = np.empty(size * 2, dtype=a.dtype)
    d[size:size + len(a)] = a
    d[size + len(a):] = e
    
    d[0] = e
    for i in range(size - 1, 0, -1):
        update(d, i, op)
    return d


@njit
def update(d, k, op):
    d[k] = op(d[2 * k], d[2 * k + 1])


@njit
def set(d, op, p, x):
    p += d.shape[0] // 2
    d[p] = x
    while p > 1:
        p >>= 1
        update(d, p, op)


@njit
def get(d, p):
    return d[p + d.shape[0] // 2]


@njit
def prod(d, op, left, right):
    size = d.shape[0] // 2
    sml = d[0]
    smr = d[0]
    left += size
    right += size

    while left < right:
        if left & 1:
            sml = op(sml, d[left])
            left += 1
        if right & 1:
            right -= 1
            smr = op(d[right], smr)
        left >>= 1
        right >>= 1

    return op(sml, smr)


@njit
def all_prod(d):
    return d[1]

'''

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])
    from nbmodule import cc
    cc.compile()
import numpy as np
from numpy import int64
from nbmodule import solve


f = open(0)
N, K = [int(x) for x in f.readline().split()]
A = np.fromstring(f.read(), dtype=int64, sep=' ')
ans = solve(N, K, A)
print(ans)

'''

import numpy as np
from numpy import int64
from numba import njit
from numba.types import i8
from numba.pycc import CC
import nbacl.segtree as seg
cc = CC('my_module')


@cc.export('solve', (i8, i8, i8[:]))
@njit
def solve(N, K, A):
    dp = np.zeros(300_001, dtype=int64)
    d = seg.segtree(dp, max, 0)
    for i in range(N):
        x = seg.prod(d, max, (A[i] - K) if A[i] > K else 0, (A[i] + K + 1) if A[i] + K < 300_000 else 300_001) + 1
        seg.set(d, max, A[i], x)
    return seg.all_prod(d)


if __name__ == '__main__':
    cc.compile()

import numpy as np
from numba import njit
from numba.types import i8


@njit
def ceil_pow2(n):
    x = 0
    while (1 << x) < n:
        x += 1
    return x


@njit
def segtree(a, op, e):
    log = ceil_pow2(a.shape[0])
    size = 1 << log
    d = np.empty(size * 2, dtype=a.dtype)
    d[size:size + len(a)] = a
    d[size + len(a):] = e
    
    d[0] = e
    for i in range(size - 1, 0, -1):
        update(d, i, op)
    return d


@njit
def update(d, k, op):
    d[k] = op(d[2 * k], d[2 * k + 1])


@njit
def set(d, op, p, x):
    p += d.shape[0] // 2
    d[p] = x
    while p > 1:
        p >>= 1
        update(d, p, op)


@njit
def get(d, p):
    return d[p + d.shape[0] // 2]


@njit
def prod(d, op, left, right):
    size = d.shape[0] // 2
    sml = d[0]
    smr = d[0]
    left += size
    right += size

    while left < right:
        if left & 1:
            sml = op(sml, d[left])
            left += 1
        if right & 1:
            right -= 1
            smr = op(d[right], smr)
        left >>= 1
        right >>= 1

    return op(sml, smr)


@njit
def all_prod(d):
    return d[1]

'''

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])
import numpy as np
from numpy import int64
from numba import njit
from numba.types import i8
import nbacl.segtree as seg


@njit((i8, i8, i8[:]), cache=True)
def solve(N, K, A):
    dp = np.zeros(300_001, dtype=int64)
    d = seg.segtree(dp, max, 0)
    for i in range(N):
        x = seg.prod(d, max, (A[i] - K) if A[i] > K else 0, (A[i] + K + 1) if A[i] + K < 300_000 else 300_001) + 1
        seg.set(d, max, A[i], x)
    return seg.all_prod(d)


f = open(0)
N, K = [int(x) for x in f.readline().split()]
A = np.fromstring(f.read(), dtype=int64, sep=' ')
ans = solve(N, K, A)
print(ans)

'''

import numpy as np
from numba import njit
from numba.types import i8


@njit
def ceil_pow2(n):
    x = 0
    while (1 << x) < n:
        x += 1
    return x


@njit
def segtree(a, op, e):
    log = ceil_pow2(a.shape[0])
    size = 1 << log
    d = np.empty(size * 2, dtype=a.dtype)
    d[size:size + len(a)] = a
    d[size + len(a):] = e
    
    d[0] = e
    for i in range(size - 1, 0, -1):
        update(d, i, op)
    return d


@njit
def update(d, k, op):
    d[k] = op(d[2 * k], d[2 * k + 1])


@njit
def set(d, op, p, x):
    p += d.shape[0] // 2
    d[p] = x
    while p > 1:
        p >>= 1
        update(d, p, op)


@njit
def get(d, p):
    return d[p + d.shape[0] // 2]


@njit
def prod(d, op, left, right):
    size = d.shape[0] // 2
    sml = d[0]
    smr = d[0]
    left += size
    right += size

    while left < right:
        if left & 1:
            sml = op(sml, d[left])
            left += 1
        if right & 1:
            right -= 1
            smr = op(d[right], smr)
        left >>= 1
        right >>= 1

    return op(sml, smr)


@njit
def all_prod(d):
    return d[1]

'''

Solution (Python):

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+1:
        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
N,K=map(int,input().split())
n=300001
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
init([0]*300001)
for i in range(N):
    A = int(input())
    a = max(A-K, 0)
    b = min(A+K, 300000)
    tmp = query(a, b+1) + 1
    update(A, tmp)
print(query(0, 300000))

Solution (Python):
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。data[0]:root<-leaf:data[-1]
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, i, v):
        '''
        leafの初期化
        i: 0-origin idx
        v: value
        '''
        self.data[i+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        data[k]=aに更新する。
        更新をrootまで更新
        '''
        k += self.n-1 
        self.data[k] = a

        while k > 0: 
            k = (k-1)//2 
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) 

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1: 
                R -= 1
                ret = self.func(ret, self.data[R-1]) 
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1 
            R >>= 1
        return ret


    def lower_bound_index(self,x,v):
        """
        x:0-origin
        [x,N)の範囲で、v<=data[j]を満たす最小のjを探す(二分探索)

        存在しないなら、float("inf")をreturn している。
        """
        
        x+=self.n-1

        
        while self.data[x]<v:
            if x%2==0: 
                if len(bin(x+1))==len(bin(x+2)):
                    x+=1
                else:
                    return float("inf")

            else:
                x>>=1

        
        while x<self.n-1:
            if self.data[2*x+1]>=v:
                x=2*x+1
            else:
                x=2*x+2
        return x-self.n+1 


N,K = map(int,input().split())
A=[int(input()) for _ in range(N)]

Seg=SegmentTree(300005, lambda a,b:max(a,b),0)

ans=0
for a in A:
    tmp = Seg.query(max(a-K,0),min(300005,a+K)+1)

    tmp+=1
    Seg.update(a,tmp)
    ans = max(tmp,ans)
print(ans)

Solution (Python):
def segfunc(x, y): return max(x, y)
def update(i, x):
    i += MAX_N-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + MAX_N
    R = r + MAX_N
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(300005).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N)
INF = 0
ans = 0




for i in a:
    tmp = query(max(i - K, 0), min(300005, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)

Solution (Python):
m,k=map(int,input().split())

n=300005

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

for _ in range(m):
    a=int(input())
    maxl=query_max(max(0,a-k),min(n-1,a+k)+1)
    update_max(a,maxl+1)

print(query_max(0,n+1))