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:
N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
#####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
tree=[0]*(N+1)
seg = SegTree(tree, segfunc, ide_ele)
Ma=max(A)
ans=0
for i in range(1,N):
    a=A[i]
    l=max(0,a-K)
    r=min(a+K,Ma)
    Ans=seg.query(l,r+1)
    seg.update(a, Ans+1)
    ans=max(ans,Ans+1)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
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
ide_ele = 0
def segfunc(x,y):
    return max(x,y)
seg=SegTree([0]*(N+4),segfunc,ide_ele)
for i in range(N):
    a=int(input())
    seg.update(a,seg.query(max(0,a-K),min(N,a+K+1))+1)
print(seg.query(0,N+3))

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
    
    if  x==n-1:
        return 1
    
    else:      
        for i in range(x+1,n):
            if abs(a[i]-a[x])<=k:
                ans=max(rec(i)+1,ans)    
        return ans

print(rec(0))

Submission status: Runtime Error

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

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

  array = [0] * n
  seg = SegTree(array, segfunc, ide_ele)
  non_select = [0] * n
  select = [0] * n
  select[0] = a[0]
  seg.update(a[0], 1)

  for i in range(1, len(a)):
    low = max(0, a[i] - k)
    high = min(a[i] + k + 1, n)
    tmp = seg.query(low, high) + 1
    
    seg.update(a[i], tmp)
    
  print(seg.query(0, n))
  
main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
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
ide_ele = 0
def segfunc(x,y):
    return max(x,y)
seg=SegTree([0]*(N+4),segfunc,ide_ele)
for i in range(N):
    a=int(input())
    seg.update(a,seg.query(max(0,a-K),min(N,a+K+1))+1)
print(seg.query(0,N+3))

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a=[int(input()) for i in range(n)]
i=0
maxs=1
#lis=[]
for i in range(n-1):
    cnt=1
    j=1
    while i<=n-2:
        if abs(a[i+j]-a[i])<=k:
            #lis.append(a[i+j])
            #print(lis)
            cnt+=1
            i+=j
            j=1
        else:
            j+=1
    maxs=max(maxs,cnt)
print(maxs)

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
    
    if  x==n-1:
        return 1
    
    else:      
        for i in range(x+1,n):
            if abs(a[i]-a[x])<=k:
                ans=max(rec(i)+1,ans)    
            return ans

print(rec(0))

Submission status: Runtime Error

Solution code:
import sys,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        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):
        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)

n,k=map(int,z().split())
M=300001
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(z())
    s[a]=1+s.query(a-k,max(a+k+1,M+1))
print(s.query(0,300001))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
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
ide_ele = 0
def segfunc(x,y):
    return max(x,y)
seg=SegTree([0]*(N+1),segfunc,ide_ele)
for i in range(N):
    a=int(input())
    seg.update(a,seg.query(max(0,a-K),min(N,a+K+1))+1)
print(seg.query(0,N+2))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
count = 0
for i in range(n):
  a = int(input())
  if i == 0:
    prev = a
  if abs(a - prev) <= k:
    if count == 0:
      if i != 0:
        count += 2
        prev = a
    else:
      count += 1
    	prev = a

print(count)

Submission status: Runtime Error

Solution code:
def recursion(arr, length, idx, value, criteria, counta):
    if idx >= length:
        return counta
    if 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 = max([recursion(arr, n, idx + 1, item, k, 0) for idx, item in enumerate(arr)])
print(result)

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


N, K, *A = map(int, open(0).read().split())
t = SegmentTree(400_000, max, 0)
dp = [1] * N
ans = 0
for i in range(N):
    a = A[i]
    t.update(a, 1 + t.query(max(1, a - K), a + K + 1))
print(t.query(0, 400_000))

Submission status: Runtime Error

Solution code:
# セグ木
# 使う操作
#####segfunc#####
def segfunc1(x, y):
    return max(x, y)
#################

#####ide_ele#####
ide_ele1 = -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())
low = [0]*(10**5 * 3 + 1)
seg = SegTree(low, segfunc1, ide_ele1)
for i in range(n):
    a = int(input())
    ma = seg.query(max(0,a-k), a+k+1)
    seg.update(a, ma+1)
ans = seg.query(0,10**5 * 3 + 1)
print(ans)

Submission status: Runtime Error

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

cnt = 0
for i in range(N):
    if abs(A[i] - A[i+1]) <= K:
        break
    cnt += 1

dq = [A[cnt]]
i = cnt + 1
while i < N:
    if abs(A[i] - A[i-1]) <= K and abs(A[i] - dq[-1]) <= K:
        dq.append(A[i])
    else:
        for s in range(1,min(len(dq), N-i-1)):
            l = abs(A[i+s] - dq[-s])
            r = abs(A[i+s+1] - A[i])
            if l <= K:
                break
            if r <= K:
                dq.append(A[i])
                i += 1
    i += 1
print(len(dq))

Submission status: Runtime Error

Solution code:
import sys,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        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):
        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)

n,k=map(int,z().split())
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(a-k,a+k+1)
print(s.query(0,300001))

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
    
    if  x==n-1:
        return 1
    
    else:      
        for i in range(x+1,n):
            if abs(a[i]-a[x])<=k:
                ans=max(rec(i)+1,ans)
                return ans

print(rec(0))

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

type segmentTree struct {
	offset int
	data   []int
	op     func(x, y int) int
	e      int
}

func newSegmentTree(n int, op func(x, y int) int, e int) segmentTree {
	var result segmentTree
	t := 1
	for t < n {
		t *= 2
	}
	result.offset = t - 1
	result.data = make([]int, 2*t-1)
	for i := 0; i < len(result.data); i++ {
		result.data[i] = e
	}
	result.op = op
	result.e = e
	return result
}

func (st segmentTree) build(a []int) {
	for i, v := range a {
		st.data[st.offset+i] = v
	}
	for i := st.offset - 1; i > -1; i-- {
		st.data[i] = st.op(st.data[i*2+1], st.data[i*2+2])
	}
}

func (st segmentTree) get(index int) int {
	return st.data[st.offset+index]
}

func (st segmentTree) update(index, value int) {
	i := st.offset + index
	st.data[i] = value
	for i >= 1 {
		i = (i - 1) / 2
		st.data[i] = st.op(st.data[i*2+1], st.data[i*2+2])
	}
}

func (st segmentTree) query(start, stop int) int {
	result := st.e
	l := start + st.offset
	r := stop + st.offset
	for l < r {
		if l&1 == 0 {
			result = st.op(result, st.data[l])
		}
		if r&1 == 0 {
			result = st.op(result, st.data[r-1])
		}
		l = l / 2
		r = (r - 1) / 2
	}
	return result
}

func main() {
	defer flush()

	N := readInt()
	K := readInt()

	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	st := newSegmentTree(300000+1, max, 0)

	t := make([]int, N)
	result := 0
	for i := 0; i < N; i++ {
		t[i] = st.query(max(A[i]-K, 0), min(A[i]+K+1, 300000+1)) + 1
		result = max(result, t[i])
		st.update(A[i], t[i])
	}
	println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}

Submission status: Runtime Error

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

b = [0] * (n+1)
ans = 0

for i in range(n):
  a = int(input())
  m = b[a] + 1
  s = max(1, a-k)
  u = min(n+1, a+k+1)
  for j in range(s, u):
    b[j] = max(b[j],m)
  if m > ans:
    ans = m

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len


    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


@mt
def slv(N, K, A):
    M = max(A)
    st = SegmentTree([0] * M, max, 0)

    for i in range(N):
        r = st.query(A[i]-K, A[i]+K+1) + 1
        st.update(A[i], r)

    return st.query(0, M)



def main():
    N, K = read_int_n()
    A = [read_int() for _ in range(N)]
    print(slv(N, K, A))

    # N = 3 * 10**5
    # K = random.randint(1, N)
    # A = [random.randint(0, N) for _ in range(N)]
    # print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
class Scc:
    def __init__(self,n):
        self.n = n
        self.edges = []

    def add_edge(self,fr,to):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        self.edges.append((fr, to))

    def scc(self):
        csr_start = [0] * (self.n + 1)
        csr_elist = [0] * len(self.edges)
        for fr,to in self.edges:
            csr_start[fr + 1] += 1
        for i in range(1,self.n+1):
            csr_start[i] += csr_start[i-1]
        counter = csr_start[:]
        for fr,to in self.edges:
            csr_elist[counter[fr]] = to
            counter[fr] += 1

        self.now_ord = self.group_num = 0
        self.visited = []
        self.low = [0] * self.n
        self.ord = [-1] * self.n
        self.ids = [0] * self.n
        def _dfs(v):
            self.low[v] = self.ord[v] = self.now_ord
            self.now_ord += 1
            self.visited.append(v)
            for i in range(csr_start[v], csr_start[v+1]):
                to = csr_elist[i]
                if self.ord[to] == -1:
                    _dfs(to)
                    self.low[v] = min(self.low[v], self.low[to])
                else:
                    self.low[v] = min(self.low[v], self.ord[to])
            if self.low[v] == self.ord[v]:
                while 1:
                    u = self.visited.pop()
                    self.ord[u] = self.n
                    self.ids[u] = self.group_num
                    if u==v: break
                self.group_num += 1
        for i in range(self.n):
            if self.ord[i] == -1: _dfs(i)
        for i in range(self.n):
            self.ids[i] = self.group_num - 1 - self.ids[i]

        groups = [[] for _ in range(self.group_num)]
        for i in range(self.n):
            groups[self.ids[i]].append(i)
        return groups

class TwoSat:
    def __init__(self,n=0):
        self.n = n
        self.answer = []
        self.scc = Scc(2*n)

    def add_clause(self, i:int, f:bool, j:int, g:bool):
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def satisfiable(self):
        g = self.scc.scc()
        for i in range(self.n):
            if self.scc.ids[2*i] == self.scc.ids[2*i+1]: return False
            self.answer.append(self.scc.ids[2*i] < self.scc.ids[2*i+1])
        return True

    def get_answer(self):
        return self.answer
N, K = map(int, input().split())
ts = TwoSat(N)
A = [int(input()) for _ in range(N)]
for i in range(1,N):
    if abs(A[i]-A[i-1]) <= K:
        ts.add_clause(A[i],True,A[i-1],True)
    else:
        ts.add_clause(A[i],False,A[i-1],False)
ts.satisfiable()
ans = 0
for i in ts.get_answer():
    if not i:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:

def recursion(arr, idx, value, criteria, counta):
    if idx >= len(arr):
        return counta
    # print(idx, value, arr[idx], 'criteria', criteria)
    if arr[idx] - value <= criteria:
        result_skip =  recursion(arr, idx + 1, value, criteria, counta)
        result_process = recursion(arr, idx + 1, arr[idx], criteria, counta+1)
        if result_skip >= result_process:
            return result_skip
        return result_process
    return recursion(arr, idx + 1, value, criteria, counta)
    

n, k = [int(i) for i in input().split()]
arr = [int(input()) for i in range(n)]
diff_arr = []
tmp = 0

result = max([recursion(arr, idx + 1, item, k, 0) for idx, item in enumerate(arr)])
print(result)

Submission status: Runtime Error

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

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

def solve(p,a):
    global N,K,A,dp
    ans = 0
    if dp[p] != -1:
        ans = dp[p]
    elif p==N-1:
        ans = 0
    elif abs(A[p]-a)>K:
        ans = solve(p+1,a)
    else:
        ans = max(solve(p+1,A[p])+1, solve(p+1,a))

    dp[p] = ans
    return ans

solve(0,0)
print(dp[0]+1)

Submission status: Runtime Error

Solution code:
class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [0] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

N,K = map(int,input().split())
ST = SegTree(300001)
for i in range(N):
    A = int(input())
    l = max(0,A-K)+1
    r = min(A+K,299999)+2
    M = ST.fold(l,r)
    ST.set_val(A+1,M+1)
print(ST.X[1])

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 - 1:
	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:
r=input().split()
N=int(r[0])
Q=int(r[1])
data="1"*N
d=[input().split() for i in range(Q)]
for i in range(Q):
    data=data[0:int(d[i][0])-1]+d[i][2]*(int(d[i][1])-int(d[i][0])+1)+data[int(d[i][1]):N]
    print(int(data)%998244353)