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:

n,k = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))
a.reverse()
# dp[i] := i番目の数字から始めたときの最大値
dp = [0 for i in range(n)]
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    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):
    # print("{} {}".format(max(a[i]-k, 0), min(max_a, a[i]+k+1)))
    dp[i] = query(max(a[i]-k, 0), min(max_a, a[i]+k+1)) + 1
    update(a[i], dp[i])
print(max(dp))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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):
    #indexがaからbまでの要素についてopの結果をｇｅｔしたい場合は.get(a,b+1)とする。
    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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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

#############
# Main Code #
#############

#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################
#####ide_ele#####
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)

# Aの部分列
# Bの隣り合う要素の絶対値がK以下

# NlogNまでいける
# セグ木？ dp?
# 全てにエッジを貼る必要はない？
# LIS?
# まあdp

# 数字iの最長はなんぼか
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))

Submission status: Accepted

Solution code:
# a_k の値を x に更新
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])
# 区間[l, r)の最小値
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))

Submission status: Accepted

Solution code:
class segment_tree():
    def __init__(self, N, function, b):
        #initialization
        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):
        # update a[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):
        #query [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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, k, a_list):
    seg_tree = SegmentTree([0] * 300001, seg_func=max, seg_func_null=0)
    for i in range(n):
        a = a_list[i]
        r = seg_tree.query(max(0, a - k), min(a + k + 1, 300001))
        seg_tree.update(a, r + 1)
    return seg_tree.query(0, 300001)


def main():
    n, k = map(int, input().split())
    a_list = [int(input()) for _ in range(n)]
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(10, 3, [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]) == 7


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
def solve1(A,K):
    INF=10**15
    MAX_A=300000
    G=segtree([0 for i in range(MAX_A+1)],max,-INF)
    dp=[0 for i in range(N)]
    dp[0]=1
    G.update(A[0],1)
    for i in range(1,N):
        #print([G.query(i,i+1) for i in range(12)])
        inf=max(0,A[i]-K)
        sup=min(MAX_A+1,A[i]+K+1)
        dp[i]=G.query(inf,sup)+1
        G.update(A[i],dp[i])
    #print(dp)
    return max(dp)

def solve2(A,K):
    N=len(A)
    dp=[1 for i in range(N)]
    for i in range(1,N):
        for j in range(i):
            if abs(A[j]-A[i])<=K:
                dp[i]=max(dp[i],dp[j]+1)
    #print(dp)
    return max(dp)

print(solve1(A,K))

Submission status: Accepted

Solution code:
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

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

def main():

    N, K = map(int, input().split())
    B = []
    for _ in range(N): B.append(int(input()))
    a = [0 for _ in range(max(B)+1)]
    ide_ele = 0
    seg = SegTree(a, segfunc, ide_ele)

    ans = 0
    for i in range(N):
        l = max(0, B[i]-K)
        r = min(len(a), B[i]+K)
        v = seg.query(l, r+1)
        ans = max(ans, max(1, v+1))
        seg.update(B[i], max(1, v+1))
        # print(ans)

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
input = stdin.buffer.readline

def main():
    n, k = map(int, input().split())

    # その値で終わる最長部分列の長さを格納
    st = SegmentTree(n=300001, default=0)

    for _ in range(n):
        a = int(input())
        st.update(a, st.query(max(0, a - k), min(300001, a + k + 1)) + 1)

    print(st.data[1])

main()

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################

#####ide_ele#####
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())
Num_max = 3*10**5 + 1

A = [int(input()) for _ in range(N)]
st = SegTree([0 for _ in range(Num_max+4)], segfunc, ide_ele)

#DP = [1 for _ in range(N)]
st.update(A[0], 0)  
for i in range(N):
  l = st.query(max(A[i] - K, 0), min(A[i] + K+1, Num_max))
  st.update(A[i], 1 + l)  
  #print(i, A[i], l, st.tree)
#print(st.tree)

print(st.query(0, Num_max))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

class SegmentTree:
    def __init__(self, a):
        # Operator
        self.op = lambda a, b : max(a, b)
        # Identity element
        self.e = 0 

        self.n = len(a)
        self.lv = (self.n - 1).bit_length()
        self.size = 2**self.lv
        self.data = [self.e] * (2*self.size - 1)
        # Bisect checking function 
        self._check = lambda x, acc : acc >= x
        self._acc = self.e

        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = self.op(self.data[i*2 + 1], self.data[i*2 + 2])

    # Update ak as x (0-indexed)
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r) (0-indexed)
    def fold(self, l, r):
        L = l + self.size; R = r + self.size
        s = self.e
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.data[R-1])
            if L & 1:
                s = self.op(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

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

aa_sorted.sort()
aas = sorted(aa)

place_list = [-1] * n
for place, (val, index) in enumerate(aa_sorted):
    place_list[index] = place

len_list = [0] * n
ST = SegmentTree(len_list)

ans = 0
for i, a in enumerate(aa):
    l = bisect.bisect_left(aas, a - k)
    r = bisect.bisect_right(aas, a + k)
    max_score = ST.fold(l, r)
    ST.update(place_list[i], max_score + 1)
    ans = max(ans, max_score + 1)
print(ans)

Submission status: Accepted

Solution code:
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
memo:
GCD... INFをide_eleに設定して、片方がINFの場合はもう片方を返す
def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else return gcd(a,b)


vl = [1,4,6,8,9]

def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''

def main():
    vl = [0]*300001
    n,k = map(int, input().split())
    st = SegTree(vl,max,0)
    for _ in range(n):
        a = int(input())
        l = max(0,a-k)
        r = min(300001,a+k+1)
        curr_max = st.query(l,r)
        st.update(a,curr_max+1)

    ans = st.query(0,300001)
    print(ans)

if __name__ == "__main__":
    main()