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: Runtime Error

Solution code:
def main():
    import sys
    from bisect import bisect_left
    N,K=list(map(int,sys.stdin.readline().split()))
    A=[0]*N
    for i in range(N):
        A[i]=int(sys.stdin.readline())

    dp=[0]*(N+1)
    dp[0]=1
    if abs(A[0]-A[1])<=K:
        dp[1]=2
    else:
        dp[1]=1
    
    for i in range(2,N):
        mx=-1
        for j in range(1,100):
            if abs(A[i-j]-A[i])<=K:
                mx=max(mx,dp[i-2]+1)

        dp[i]=mx        

    print(max(dp))


main()

Submission status: Runtime Error

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

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
seg = SegTree(N,max,0)
seg.build([0]*N)
*A,=[int(input()) for _ in range(N)]
for i in range(N):
  a = A[i]
  tmp = seg.fold(max(0,a-K),min(N,a+K+1))
  seg.set_val(a,tmp+1)

print(seg.fold(0,N))

Submission status: Runtime Error

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


ans = []

i = 0
while(i<=N-2):
  a = A[i]
  T = 1
  while (j<=N-1):
    if ( abs(a-A[j]) <= K ):
      T += 1
      a = A[j]
    j += 1
  ans.append(T)
  i += 1
  
print(max(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
a=np.array(a)
n,k = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))

for i in range(n-1):
    b = list(map(lambda x,y: x-y, a, a))
    if abs(b) >= 3:
        count += 1
        print(count)

Submission status: Runtime Error

Solution code:
row = input().split()
N = int(row[0])
K = int(row[1])

An = []

for i in range(0, N):
    An.append(input().split())

print(An)

for i in range(0, N-2):
    Bn = abs(An[i] - An[i+1])

cnt = 0
Cn = []

for i in range (len(Bn)):
    if Bn[i] <= K:
        cnt += 1
        Cn.append(cnt)
    else:
        cnt = 0

print(max(Cn))

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
dp = np.ones((N+1, 300000+1)) * -1

for i in range(N):
    A = int(input())
    if dp[i, A] < 0:
        dp[i, A] = 0
    for j in np.where(dp[i,:] > -1)[0]:
        if dp[i+1, j] < 0:
            dp[i+1, j] = dp[i, j]
        if (abs(A - j) <= K) and (dp[i+1, A] < (dp[i, j] + 1)):
            dp[i+1, A] = dp[i, j] + 1
print(int(np.max(dp[N])))

Submission status: Runtime Error

Solution code:
import sys
try:sys.stdin,sys.stdout=open('in.txt','r'),open('out.txt','w')
except:pass
ii1=lambda:int(sys.stdin.readline().strip()) # for interger
is1=lambda:sys.stdin.readline().strip() # for str
iia=lambda:list(map(int,sys.stdin.readline().strip().split())) # for List[int]
isa=lambda:sys.stdin.readline().strip().split() # for List[str]
mod=int(1e9 + 7);from collections import *;from math import *

###################### Start Here ######################

n , k = iia()
arr = []
for _ in range(n):arr.append(ii1())
dp=[0]*n
dp[0]=1
# print(arr)
for i in range(n-1):
    if abs(arr[i+1]-arr[i])<=k:
        dp[i+1]=max(dp[i-1],dp[i])+1
    else:
        dp[i+1]=max(dp[i])
# print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
n, k = map(lambda x: int(x), input().split())

list_a = []
for _ in range(n):
     list_a.append(int(input()))
        
memo = dict()


def subilst_max_length(current_value, i):
    if (current_value, i) in memo.keys():
        return memo[(current_value, i)]
    if i == n-1:
        if (current_value is None) or (abs(current_value - list_a[i]) <= k):
            memo[(current_value, i)] = 1
            return 1
        memo[(current_value, i)] = 0
        return 0
    
    if (current_value is None) or (abs(current_value - list_a[i]) <= k):
        # iの値をsublistに含めるor含めない
        memo[(current_value, i)] = max(1+subilst_max_length(list_a[i], i+1), subilst_max_length(current_value, i+1))
        return memo[(current_value, i)]
    memo[(current_value, i)] = subilst_max_length(current_value, i+1)
    return memo[(current_value, i)]
  
print(subilst_max_length(None, 0))

Submission status: Runtime Error

Solution code:
n,q = input().split(' ')
n = int(n)
q=int(q)
s=''
a =[]
for i in range(n):
        s+='1'
c=''
for _ in range(q):
   a,b,c=input().split(' ')
   a=int(a)
   b=int(b)
   for i in range(a,b):
       s+=c;
   print(s)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=[None]*n
m=0
lian=0
a0=int(input())
a[0]=a0
for i in range(1,n):
  a1=int(input())
  a[i]=a1
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m:
      m=lian
    a0=int(a1)
m1=0
lian=0
a0=a[n-1]
for i in range(2,n+1):
  a1=a[n-i]
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m1:
      m1=lian
    a0=int(a1)
m2=0
lian=0
a0=a[n-2]
for i in range(3,n+1):
  a1=a[n-i]
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m2:
      m2=lian
    a0=int(a1)
if m>m1:
  m1=m
  #print(m+1)
else:
  if m2>m1:
  m1=m2
print(m1)

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
dp = np.ones((N+1, 300000)) * -1

for i in range(N):
    A = int(input())
    if dp[i, A] < 0:
        dp[i, A] = 0
    for j in np.where(dp[i,:] > -1)[0]:
        if dp[i+1, j] < 0:
            dp[i+1, j] = dp[i, j]
        if (abs(A - j) <= K) and (dp[i+1, A] < (dp[i, j] + 1)):
            dp[i+1, A] = dp[i, j] + 1
print(int(np.max(dp[N])))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve_0_WA(N, K, AS):
    candidates = [[0]]
    for i in range(1, N):
        A = AS[i]
        new_candidates = []
        for c in candidates:
            if abs(AS[c[-1]] - A) <= K:
                new_candidates.append(c[:])
                c.append(i)
                new_candidates.append(c)
                break
            else:
                new_candidates.append(c)
        else:
            new_candidates.append([i])
        candidates = new_candidates
        candidates.sort(key=len, reverse=True)
        debug("candidates", candidates)
    return len(candidates[0])


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    global WIDTH
    WIDTH = width
    set_depth((width - 1).bit_length() + 1)


def point_set(table, pos, value, binop):
    pos = pos + NONLEAF_SIZE
    table[pos] = value
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
        )


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += SEGTREE_SIZE // 2
    right += SEGTREE_SIZE // 2
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def bisect_left(table, left, right, value):
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    left_left = None
    right_left = None
    while left < right:
        if left & 1:
            if left_left is None and table[left] >= value:
                left_left = left
            left += 1
        if right & 1:
            if table[right - 1] >= value:
                right_left = right - 1
        left >>= 1
        right >>= 1

    if left_left is not None:
        pos = left_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    elif right_left is not None:
        pos = right_left
        while pos < NONLEAF_SIZE:
            if table[2 * pos] >= value:
                pos = 2 * pos
            else:
                pos = 2 * pos + 1
        return pos - NONLEAF_SIZE
    else:
        return WIDTH


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def solve(N, K, AS):
    count = [0] * 300_000
    count[AS[0]] = 1
    for i in range(1, N):
        A = AS[i]
        start = max(0, A - K)
        best = max(count[start:A + K + 1])
        count[A] = best + 1
    return max(count)


def main():
    # parse input
    N, K = map(int, input().split())
    AS = []
    for _i in range(N):
        AS.append(int(input()))

    print(solve(N, K, AS))


# tests
T1 = """
10 3
1
5
4
3
8
6
9
7
2
4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
7
"""

T2 = """
6 2
5
7
3
3
3
3
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
5
"""

T3 = """
6 2
5
7
3
3
3
3
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())

l=[]
for i in range(n):
  a=int(input())
  l.append(a)

sa=[]
ss=[]
for i in range(n-1):
  sa.append(l[i]-l[i+1])

for i in range(len(sa)-1):
  if len(sa)<=i:
    break
  if k<abs(sa[i]) and abs(sa[i]+sa[i+1])<=k:
    sa[i]=l[i]-l[i+2]
    sa.pop(i+1)

print(len(sa)+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

def recursion(arr, length, idx, value, criteria, counta):
    if idx >= length:
        return counta
    if abs(arr[idx] - value) <= criteria:
        result_skip =  recursion(arr, length, idx + 1, value, criteria, counta)
        result_process = recursion(arr, length, idx + 1, arr[idx], criteria, counta+1)
        if result_skip >= result_process:
            return result_skip
        return result_process
    return recursion(arr, length, idx + 1, value, criteria, counta)
    
n, k = [int(i) for i in input().split()]
arr = [int(input()) for i in range(n)]

result = recursion(arr, n, 1, item, k, 0)
print(result)

Submission status: Runtime Error

Solution code:
def main():
    
    n, k = map(int, input().split())
    a = [0]
    for _ in range(n):
        a.append(int(input()))
    table = [0]*(n+1)
    dp = [0]*(n+1)
    
    for i in range(1, n+1):
        down = a[i]-k
        up = a[i]+k
        if down < 0:
            down = 0
        if up > n:
            up = n
        dp[i] = max(table[down:up+1])+1
        table[a[i]] = dp[i]
    
    print(dp[-1])

main()

Submission status: Runtime Error

Solution code:
#input

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

def input_2(n,k):
    n, k = map(int,input().split())
    a = [randint(1, k) for i in range(n)]
    return n,k,a

def connect(i,d,p,q):
    if i+d >= n:
        if p > q:
            q = p
        #print("bbbb {} {}".format(p,q))
        return q

    if max(a[i] - a[i+d], a[i+d] - a[i]) <= k:
        #print("aaaa {} {}".format(p+1,q))
        q = connect(i+d,1,p+1,q)
    else:
        #print("aaaa {} {}".format(p,q))
        q = connect(i,d+1,p,q)

    return q

def main():
    #n,m,brg = input_1()
    #n,m,brg = input_2(300000,300000)

    ans = 0

    i = 0
    while i < (n - ans):
        q = connect(i,1,1,1)
        if q > ans:
            ans = q
        i += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [0] * N
for i in range(N):
	A[i] = int(input())
ans = 0
i, j = 0, 1
while i < N - 2:
	if abs(A[i] - A[j]) <= K:
		ans += 1
		i = j
	j += 1
if ans > 0:
	ans += 1
print(ans)

Submission status: Runtime Error

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

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


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

Submission status: Runtime Error

Solution code:
def solve(city_arr, road_arr):
    # points = [road_arr[0][0],road_arr[0][1]]
    starts = [road[0] for road in road_arr]
    ends = [road[1] for road in road_arr]
    points = starts
    points.extend(ends)
    set_cities = set(points)
    used = [False for road in road_arr]
    is_end = True
    counta = 0
    idx = 0
    current = ends[0]
    used[0] = True
    while all(used):
        try:
            idx = starts.index(current)
            used[idx] = True
            current = ends[idx] if is_end else starts[idx]
        except:
            counta +=1
            try:
                idx = used.index(False)
                current = ends[idx] if is_end else starts[idx]
            except:
                counta += len(city_arr) - len(points) - 1
                return counta
    return counta

    
if __name__ == '__main__':
    num_cities, num_roads = [int(i) for i in input().split()]
    roads = [[int(i) for i in input().split()] for j in range(num_roads)]
    cities = range(1, num_cities + 1)
    ans = solve(cities, roads)
    print(ans)

Submission status: Runtime Error

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

def rec(x):
    ans=1
    for i in range(x+1,n):
        if abs(a[i]-a[x])<=k:
            ans=max(rec(i)+1,ans)    
    return ans

b=0
for i in range(n):
    b=max(b,rec(i))
print(b)

Submission status: Runtime Error

Solution code:
def FlatSub():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    diff = []
    ans, count = 0, 0

    for i in range(n-1):
        num = a[i+1]-a[i]
        diff.append(num)
        if abs(num) <= k:
            count += 1
        else:
            ans = max(ans, count)
            count = 0 
        
    count = 0
    for i in range(1, n-1):
        if abs(diff[i]) <= k:
            count += 1
        else:
            if abs(diff[i+1]+diff[i]) <= k or abs(diff[i-1]+diff[i]) <= k:
                continue
            else:
                ans = max(count, ans)
                count = 0
            
    print(max(ans, count)+1)
    
if __name__ == '__main__':
    FlatSub()

Submission status: Runtime Error

Solution code:
def flat(a,k):
	if len(a) == 1:
		return a
	ab = a.pop(-1)
	b = flat(a,k)
	if abs(b[-1] - ab) <= k:
		b.append(ab)
	return b



n,k = map(int,input().split())
a = []
for i in range(n):
	ain = int(input())
	a.append(ain)
b = flat(a,k)
print(len(b))

Submission status: Runtime Error

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

def init_max(init_max_val):
    #set_val
    for i in range(N):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    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 = -1

#num_max:n以上の最小の2のべき乗
num_max =2**(N-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

a = [0]*N
init_max(a)

for _ in range(N):
    a = int(input())-1
    x = query_max(max(0, a-K), min(N, a+K+1))
    update_max(a, x+1)

print(query_max(0, N))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [0]
for _ in range(n):
    a.append(int(input()))
a.append(0)
table = [0]*(n+1)
dp = [0]*(n+1)

for i in range(1, n+1):
    down = a[i]-k
    up = a[i]+k
    if down < 1:
        down = 1
    if up > n:
        up = n
    dp[i] = max(table[down:up+1])+1
    table[a[i]] = dp[i]

print(dp[-1])

Submission status: Runtime Error

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

    def debug(self):
        def full_tree_pos(G):
            n = G.number_of_nodes()
            if n == 0: return {}
            pos = {0: (0.5, 0.9)}
            if n == 1: return pos
            i = 1
            while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1
            height = i
            p_key, p_y, p_x = 0, 0.9, 0.5
            l_child = True
            for i in range(height):
                for j in range(2 ** (i + 1)):
                    if 2 ** (i + 1) + j - 1 < n:
                        if l_child == True:
                            pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            l_child = False
                        else:
                            pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
                            l_child = True
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            p_key += 1
                            (p_x, p_y) = pos[p_key]
            return pos

        import networkx as nx
        import matplotlib.pyplot as plt
        A = self.tree[1:]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("tree-{0}.png".format(self.plt_cnt))
        plt.clf()

        A = self.lazy[1:-1]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("lazy-{0}.png".format(self.plt_cnt))
        plt.clf()
        self.plt_cnt += 1

##################################################################################################################
import sys
input = sys.stdin.readline

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

# クエリ関数
ef = 0
f = lambda x, y : x if x > y else y
# 更新関数（g が局所的か要確認）
eh = -1
h = lambda x, y: x if x != eh else y
g = lambda x, y: x
st = LazySegmentTree(N, f, g, h, ef, eh)

for _ in range(N):
    A = int(input())
    x = st.get_range(A-K//2,A+K//2+2)
    st.update_range(A-K//2,A+K//2+2, x+1)
print(max(st))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
N, K = map(int, input().split())

A = [int(input()) for i in range(N)]

memo = {}


def solve(n, v):
    if (n, v) in memo:
        return memo[(n, v)]
    if n == N - 1:
        if abs(v - A[n]) <= K:
            return 1
        else:
            return 0
    else:
        if abs(v - A[n]) <= K:
            res = max([solve(n + 1, A[n]) + 1, solve(n + 1, v)])
            memo[(n, v)] = res
            return res
        else:
            res = solve(n + 1, v)
            memo[(n, v)] = res
            return res


print(solve(0, A[0]))

Submission status: Runtime Error

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

mod = 998244353

l = []
t = ''
for i in range(20000):
    t += '1'
for i in range(1, 10):
    l.append(str(int(t) * i))

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    t = l[LRD[i][2] - 1]
    while len(t) < LRD[i][1] - LRD[i][0] + 1:
        t += t
    S = S[:LRD[i][0] - 1] + t[:LRD[i][1] - LRD[i][0] + 1] + S[LRD[i][1]:]
    print(int(S) % mod)

Submission status: Runtime Error

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

A = [int(input()) for i in range(N)]

memo = {}


def solve(n, v):
    if (n, v) in memo:
        return memo[(n, v)]
    if n == N - 1:
        if abs(v - A[n]) <= K:
            return 1
        else:
            return 0

    else:
        if abs(v - A[n]) <= K:
            res = max([solve(n + 1, A[n]) + 1, solve(n + 1, v)])
            memo[(n, v)] = res
            return res
        else:
            res = solve(n + 1, v)
            memo[(n, v)] = res
            return res


print(solve(0, A[0]))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
M = 20
P = [0 for k in range(M+1)]
for i in range(N):
  a = int(input())
  c = max(P[max(a - K, 0):min(a+K+1, M+1)]) + 1
  P[a] = max(P[a], c)
print(max(P))

Submission status: Runtime Error

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

l=[]
for i in range(N):
    l.append(int(input()))
    

ll=[]

def s(n,l,ll,K):  
    for i in range(n+1,len(l)):
        if abs(l[n]-l[i]) <= K:
            ll.append(l[n])
            return(i)
        else:
            continue
    return

i=0
while True:
    j=s(i,l,ll,K)
    i=j
    if i == len(l)-1:
        break

if abs(l[len(l)-1]-l[len(l)-2]) <= K:
    ll.append(l[len(l)-1])

print(len(ll))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

N = []
for i in range(n):
    N.append(int(input()))

# 隣同士がいくつ離れているかをカウント
dist = [0 for _ in range(n + 3)]
for i in range(1, n):
    dist[abs(N[i] - N[i - 1])] += 1

ans = 0

for i in range(k + 1):
    ans += dist[i]

# print(dist)
print(ans + 1)

Submission status: Runtime Error

Solution code:
from collections import deque

N,K = list(map(int,input().split()))
A = [int(input()) for i in range(N)]
if N == 1:
    print(1)
    exit()

lst = [-1]*(N+1)
queue = deque()
queue.append((A[0],1,1))
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
            lst[r] = size+1
        else:
            queue.append((r,size,i+1))
            lst[r] = size
print(max(lst))