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: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def li():  return list(mi())


def solve():
    n, k = mi()

    stack = []

    for i in range(n):
        z = ii()
        if not stack:
            stack.append(z)
        else:
            d = abs(stack[-1] - z)
            if d <= k:
                stack.append(z)

    return len(stack)
    
def main():
    # pass
    print(solve())


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegTree:
	"""
	1-indexed
	"""
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		# num:size以上の最小の2のべき乗
		self.datSize = 2**size.bit_length()

		# the tree is implemented by sequencial list
		# (1-indexed, 0 is not use.)
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		"""
		i: index(1-ordered)
		"""
		# i -= 1	# 1-orderで指定され、内部では0-Order想定?
		# i += (self.datSize - 1)
		i += self.datSize
		self.datTree[i] = val
		while 1 < i:
			i >>= 1
			self.datTree[i] = self.compareFunc( self.datTree[i<<1|0], self.datTree[i<<1|1] )

	def query(self,a,b):
		return self.query_(a,b,1,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex(not use)
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:
			if b & 1:
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b])

			if a & 1:
				ret = self.compareFunc(ret, self.datTree[a])
				a += 1

			a >>= 1; b >>= 1

		return ret

	def printTree(self):
		print(self.datTree)

def LongestSeaquence(A,K):
	N = len(A)
	lis = 0

	# === Range Maximum Query ===
	MAX_A = max(A)
	tree = SegTree(MAX_A,max,0,-1e18)
	# tree.update( 0, 1 )

	for n in range(N):
		x = A[n]
		l = max(0,x-K-1)
		r = min(MAX_A,x+K+1)	# 半開区間
		tree.update( x, tree.query(l,r)+1 )

	lis = tree.query(0,MAX_A)

	return lis

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

	print(LongestSeaquence(A,K))



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, lis, ele, op):
        self.len = len(lis)
        self.n = 1 << ((self.len - 1).bit_length())
        self.op = op
        self.ele = ele
        self.tree = self._build(lis)
    def _build(self, lis):
        res_tree = [self.ele] * (self.n - 1) + lis + [self.ele] * (self.n - self.len)
        for i in range(self.n - 2, -1, -1):
            res_tree[i] = self.op(res_tree[i * 2 + 1], res_tree[i * 2 + 2])
        return res_tree
    def __get__(self, i):
        return self.tree[self.n + i - 1]
    def update(self, i, x):
        i += self.n - 1
        self.tree[i] = x
        while i > 0:
            i -= 1
            i >>= 1
            self.tree[i] = self.op(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    def query(self, l, r):
        l +=  self.n - 1
        r += self.n - 1
        L = self.ele
        R = self.ele
        while l < r:
            if l & 1 == 0:
                L = self.op(L, self.tree[l])
                l += 1
            if r & 1 == 0:
                r -= 1
                R = self.op(R, self.tree[r])
            l -= 1
            l >>= 1
            r >>= 1
        return self.op(L, R)
n, k = map(int, input().split())
ST = SegmentTree([0] * 400000, 0, max)
for i in range(n):
    a = int(input())
    res = ST.query(max(0, a - k), min(400000, a + k + 1))
    ST.update(a, res + 1)
print(ST.tree[1])

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, lis, ele, op):
        self.len = len(lis)
        self.n = 1 << ((self.len - 1).bit_length())
        self.op = op
        self.ele = ele
        self.tree = self._build(lis)
    def _build(self, lis):
        res_tree = [self.ele] * (self.n - 1) + lis + [self.ele] * (self.n - self.len)
        for i in range(self.n - 2, -1, -1):
            res_tree[i] = self.op(res_tree[i * 2 + 1], res_tree[i * 2 + 2])
        return res_tree
    def __get__(self, i):
        return self.tree[self.n + i - 1]
    def update(self, i, x):
        i += self.n - 1
        self.tree[i] = x
        while i > 0:
            i -= 1
            i >>= 1
            self.tree[i] = self.op(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    def query(self, l, r):
        l +=  self.n - 1
        r += self.n - 1
        L = self.ele
        R = self.ele
        while l < r:
            if l & 1 == 0:
                L = self.op(L, self.tree[l])
                l += 1
            if r & 1 == 0:
                r -= 1
                R = self.op(R, self.tree[r])
            l -= 1
            l >>= 1
            r >>= 1
        return self.op(L, R)
n, k = map(int, input().split())
ST = SegmentTree([0] * 300000, 0, max)
for i in range(n):
    a = int(input())
    res = ST.query(max(0, a - k), min(300000, a + k + 1))
    ST.update(a, res + 1)
print(ST.tree[1])

Submission status: Wrong Answer

Solution code:
class SegmentTree: #1-indexed
    def __init__(self,list,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 #木の高さ
        self.zero=2**(self.height-1) #最下段に添字を合わせる用
        self.id=inf #単位元
        self.tree=[self.id]*(2**self.height) #木を単位元で初期化
        self.f=f
        for i in range(len(list)):
            self.tree[self.zero+i]=list[i]
        for i in range(self.zero-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): #i番目の要素をxに変更
        i+=self.zero
        self.tree[i]=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r): #区間[l,r)
        l+=self.zero
        r+=self.zero
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)

    '''
    FFFFTTTTとしたときの最小のTを求める
    '''
    def BinarySearch(self,l,r,f): #fの返り値はboolにする
        if not f(self.query(l,r)): #そもそも区間内にTがなければ右端をreturn
            return r
        l+=self.zero
        while True:
            if f(self.tree[l]):
                if l>=self.zero:
                    return l-self.zero+1 #最下段ならreturn
                else:
                    l*=2 #左の子供を見る
            else:
                if l%2==0:
                    l+=1 #左の子なら右を見る
                else:
                    l=(l//2)+1 #右の子なら親の右を見る

n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
am=300005
S=SegmentTree([0]*am,max)
for i in range(n):
    x=S.query(max(0,a[i]-k-1),min(a[i]+k+1,am))+1
    S.update(a[i]-1,x)
print(S.query(0,am))

Submission status: Wrong Answer

Solution code:
class SegmentTree: #1-indexed
    def __init__(self,list,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 #木の高さ
        self.zero=2**(self.height-1) #最下段に添字を合わせる用
        self.id=inf #単位元
        self.tree=[self.id]*(2**self.height) #木を単位元で初期化
        self.f=f
        for i in range(len(list)):
            self.tree[self.zero+i]=list[i]
        for i in range(self.zero-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): #i番目の要素をxに変更
        i+=self.zero
        self.tree[i]=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r): #区間[l,r)
        l+=self.zero
        r+=self.zero
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)

    '''
    FFFFTTTTとしたときの最小のTを求める
    '''
    def BinarySearch(self,l,r,f): #fの返り値はboolにする
        if not f(self.query(l,r)): #そもそも区間内にTがなければ右端をreturn
            return r
        l+=self.zero
        while True:
            if f(self.tree[l]):
                if l>=self.zero:
                    return l-self.zero+1 #最下段ならreturn
                else:
                    l*=2 #左の子供を見る
            else:
                if l%2==0:
                    l+=1 #左の子なら右を見る
                else:
                    l=(l//2)+1 #右の子なら親の右を見る

n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
am=300005
S=SegmentTree([0]*am,max)
for i in range(n):
    x=S.query(max(0,a[i]-k-1),min(a[i]+k,am-1)+1)
    S.update(a[i]-1,x+1)
print(S.query(0,am))

Submission status: Wrong Answer

Solution code:
class SegmentTree: #1-indexed
    def __init__(self,list,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 #木の高さ
        self.zero=2**(self.height-1) #最下段に添字を合わせる用
        self.id=inf #単位元
        self.tree=[self.id]*(2**self.height) #木を単位元で初期化
        self.f=f
        for i in range(len(list)):
            self.tree[self.zero+i]=list[i]
        for i in range(self.zero-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): #i番目の要素をxに変更
        i+=self.zero
        self.tree[i]=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r): #区間[l,r)
        l+=self.zero
        r+=self.zero
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)

    '''
    FFFFTTTTとしたときの最小のTを求める
    '''
    def BinarySearch(self,l,r,f): #fの返り値はboolにする
        if not f(self.query(l,r)): #そもそも区間内にTがなければ右端をreturn
            return r
        l+=self.zero
        while True:
            if f(self.tree[l]):
                if l>=self.zero:
                    return l-self.zero+1 #最下段ならreturn
                else:
                    l*=2 #左の子供を見る
            else:
                if l%2==0:
                    l+=1 #左の子なら右を見る
                else:
                    l=(l//2)+1 #右の子なら親の右を見る

n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
am=300005
S=SegmentTree([0]*am,max)
for i in range(n):
    x=S.query(max(0,a[i]-k-1),min(a[i]+k,am))
    S.update(a[i]-1,x+1)
print(S.query(0,am))

Submission status: Wrong Answer

Solution code:
import math

N, K = map(int, input().split())
Amax = 300000
# seg_leaf : seg_tree の葉で [0:0) に当たるノードのインデックス
seg_leaf_0 = 2**math.ceil(math.log2(Amax+1))
# seg_tree : 1-indexed のセグ木
seg_tree = [0]*(seg_leaf_0 * 2)

def get_max(check_min, check_max, area_min, area_max, node_ind):
    if area_max < check_min or check_max < area_min:
        return 0
    elif check_min <= area_min and area_max <= check_max:
        return seg_tree[node_ind]
    else:
        v1 = get_max(check_min, check_max, area_min, (area_min + area_max)//2, node_ind * 2)
        v2 = get_max(check_min, check_max, (area_min + area_max)//2 + 1, area_max, node_ind * 2 + 1)
        return(max(v1, v2))

def update(node_ind, value):
    seg_tree[node_ind] = value
    if node_ind != 1:
        update(node_ind//2, value)

for _ in range(N):
    A = int(input())
    x = get_max(max(A-K, 0), min(A+K, Amax), 0, seg_leaf_0 - 1, 1)
    update(seg_leaf_0 + A, x + 1)

print(seg_tree[1])

Submission status: Wrong Answer

Solution code:

import sys
# sys.setrecursionlimit(100000)


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 SegmentTree:
    x_unit = 0
    x_f = max
    # 1-based index

    def __init__(self, n: int):
        self.n = n
        self.tree = [self.x_unit] * (n + n)

    def build(self, seq):
        for i, x in enumerate(seq, self.n):
            self.tree[i] = x
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.x_f(self.tree[i << 1], self.tree[i << 1 | 1])

    def set_val(self, i, x):
        """value update"""
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.x_f(self.tree[i << 1], self.tree[i << 1 | 1])

    def fold(self, L, R):
        """range query"""
        L += self.n
        R += self.n
        vL = vR = self.x_unit
        while L < R:
            if L & 1:
                vL = self.x_f(vL, self.tree[L])
                L += 1
            if R & 1:
                vR = self.x_f(vR, self.tree[R])
                R -= 1
            L >>= 1
            R >>= 1
        return self.x_f(vL, vR)


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

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

    print(segtree.tree[1])

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)
        self.rank = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        rx, ry = self.rank[x],self.rank[y]
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy
        self.rank[x] +=1

    def same(self,x,y):
        return self[x] == self[y]

    def find_max(self):
        return max(self.size)

N,K = map(int, input().split())
A = [0] + [int(input()) for _ in range(N)]
uf = UnionFind(N)
merge = uf.merge
same = uf.same

for i in range(1,N+1):
    pls ,mns =False, False
    number = A[i]
    for j in range(i+1,N):
        if pls:
            if -K <= A[j] - number < 0:
                merge(i, j)
                #print(A[i],A[j],i,j)
                break
        elif mns:
            if 0 <= A[j] -number <= K:
                merge(i, j)
                #print(A[i],A[j],i,j)
                break
        else:
            if -K <= A[j]- number <= K:
                merge(i,j)
                #print(A[i], A[j], i, j)
            pls,mns = A[j]-number>=0, A[j]-number <0

print(uf.find_max()-1)

Submission status: Wrong Answer

Solution code:
"""
ACL0926_D
"""
import numpy as np

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

b[0]=a[0]
a[0]=0

for i in range(1,n):
    for j in range(0,n-1):
        c[j]=abs(a[j]-b[i-1])
        if c[j]>k:
            c[j]=0
    max_index=np.argmax(c)
    b[i]=a[max_index]
    a[max_index]=0

for i in range(n):
    if b[i]==0:
        for j in range (i,n):
            b[j]=0
            
ans=np.count_nonzero(b)
print(b)
print(ans)

Submission status: Wrong Answer

Solution code:

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

#####ide_ele　単位元#####
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=map(int,input().split())
A=[int(input()) for i in range(n)]

T=[0 for i in range(300000+1)]
T=SegTree(T,segfunc,ide_ele)

for num in A:
    now=T.query(max(0,num-k),min(num+k+1,n))
    #print(now)
    T.update(num,now+1)

print(T.query(0,n+1))

Submission status: Wrong Answer

Solution code:

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

#####ide_ele　単位元#####
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=map(int,input().split())
A=[int(input()) for i in range(n)]

T=[0 for i in range(300000+1)]
T=SegTree(T,segfunc,ide_ele)

for num in A:
    now=T.query(max(0,num-k),min(num+k+1,n))
    T.update(num,now+1)

print(T.query(0,n))

Submission status: Wrong Answer

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

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=3*10**5+1
seg=[ide_ele]*2*num

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

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

cnt = [[] for _ in range(max(A) + 1)]

graph = [[] for _ in range(N)]

for i in range(N):
    cnt[A[i]].append(i)

for i in range(N):
    for j in range(max(1, A[i] - 3), min(len(cnt), A[i] + 4)):
        if len(cnt[j]) > 0:
            ind = bisect.bisect_left(cnt[j], i)
            if ind < len(cnt[j]) and cnt[j][ind] > i:
                graph[i].append(cnt[j][ind])

start = 0
res = 0
dist = [-1]*N

for i in range(N):
    if N - i < res:
        break

    if dist[i] >= 0:
        continue

    q = deque([i])
    dist[i] = 1

    while q:
        v = q.pop()
        for n_v in graph[v]:
            dist[n_v] = max(dist[n_v], dist[v] + 1)
            q.append(n_v)

    res = max(res, max(dist))

print(max(dist))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 22
#scale = 3
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1))
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,i,maxi)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
list = [int(input()) for _ in range(N)]


new_list = []
new_list.append(list[0])

for i in range(N):
    if i + 1 == N:
        break
  
    did = abs(new_list[-1] - list[i + 1])
   
    if did <= K:
        new_list.append(list[i + 1])
        
print(len(new_list))

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

cnt = [[] for _ in range(max(A) + 1)]

graph = [[] for _ in range(N)]

for i in range(N):
    cnt[A[i]].append(i)

for i in range(N):
    for j in range(max(1, A[i] - 3), min(len(cnt), A[i] + 4)):
        if len(cnt[j]) > 0:
            ind = bisect.bisect_left(cnt[j], i)
            if ind < len(cnt[j]) and cnt[j][ind] > i:
                graph[i].append(cnt[j][ind])

start = 0
res = 0
dist = [-1]*N

for i in range(N):
    if dist[i] >= 0:
        continue

    q = deque([i])
    dist[i] = 1

    while q:
        v = q.pop()
        for n_v in graph[v]:
            dist[n_v] = max(dist[n_v], dist[v] + 1)
            q.append(n_v)

    res = max(res, max(dist))

print(max(dist))

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase

class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        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 __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

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

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

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

def main():
    mxn = int(3e5) + 5
    n, k = getints()
    a = []
    for _ in range(n):
        a.append(getint())
    st = SegmentTree([0] * mxn)
    for i in a:
        q = st.query(max(i - k, 0), min(mxn, i + k + 1))
        st[i] = q + 1
    print(st.query(0, n))


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 21
#scale = 3
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1))
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,i,maxi)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])