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:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        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 __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] = max(q,self._lazy[2 * idx])
        self._lazy[2 * idx + 1] = max(q,self._lazy[2 * idx+1])
        self.data[2 * idx] = max(q,self.data[2 * idx])
        self.data[2 * idx + 1] = max(q,self.data[2 * idx])

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1],self._lazy[idx])
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start <= stop:
            if start & 1:
                self._lazy[start] = max(value,self._lazy[start])
                self.data[start] = max(value,self.data[start])
                start += 1
            if (stop+1) & 1:
                self._lazy[stop] = max(value, self._lazy[start])
                self.data[stop] = max(value, self.data[start])
                stop-=1
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy)

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

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop)

        res = default
        while start <= stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if (stop+1) & 1:

                res = self._func(res, self.data[stop])
                stop -= 1
            start >>= 1
            stop >>= 1
        return res

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




n,k=mdata()
a=[int(data()) for i in range(n)]
S=LazySegmentTree([0]*(max(a)+1))
ans=0
for i in a:
    a1=S.query(i-1,i-1)
    S.add(i-k-2,i+k-1,a1+1)
    ans = max(ans, a1)
    s1=[]
ans=max(ans,S.query(a[-1]-1,a[-1]-1))
out(ans)

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))
ans = 0
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        ans = max(ans,size)
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
        else:
            queue.append((r,size,i+1))
        lst[r] = size
print(ans)

Submission status: Runtime Error

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

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in l[i + 1: i + 100]:
        if abs(i - j) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [[-1] for i in range(300010)]
d = [0] * N
for i in range(N):
    d[i] = int(input())
    A[d[i]].append(i)

c = [[0] * 2 for i in range(N)]

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

#####ide_ele#####
ide_ele = -float("INF")
#################

a = [0] * 300010
for i in range(300001):
    a[i] = A[i][-1]

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

seg = SegTree(a, segfunc, ide_ele)

for i in range(N-1, -1, -1):
    del A[d[i]][-1]
    seg.update(d[i] ,A[d[i]][-1])
    s = min(d[i] + K + 1, 300001)
    t = max(d[i] - K, 1)
    c[i][0] = seg.query(d[i], s)
    c[i][1] = seg.query(t, d[i]+1)
    #print(A[:10])


dp = [1] * (N + 2)
ans = 0
for i in range(N-1, -1, -1):
    dp[c[i][0]] = dp[i] + 1
    dp[c[i][1]] = dp[i] + 1
    ans = max(ans, dp[i])

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def func(i,j,k,K, A):
    if abs(A[i] - A[j]) <= K:
        return i, j
    elif abs(A[i] - A[k]) <= K:
        return i, k
    elif abs(A[j] - A[k]) <= K:
        return j, k
    else:
        return 0,0
    
def solve(N: int, K: int, A: "List[int]"):
    if N == 1:
        print(0)
        return
    if N ==2:
        if abs(A[0] - A[1]) <= K:
            print(2)
        else:
            print(0)

    i, j , k = 0, 1, 2
    ans = []
    while i <= N - 1:
        n, m = func(i, j, k, K, A)
        # print(i,j,k,n,m)
        if n != m:
            ans.append(A[n])
            i = m
            j = i + 1

        else:
            j += 1 

        if j+1<N:
            k = j + 1
        else:
            k = j 

        if j == k :
            i = i + 1
            j = i + 1
            k = j + 1

    if m !=0:
        ans.append(m)
    print(len(ans))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

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

print(rec(0))

Submission status: Runtime Error

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

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 0
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

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

print(query(0, N))

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))
ans = 0
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        ans = max(ans,size)
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
        else:
            queue.append((r,size,i+1))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, k = I()

cache = [0] * 300001

for _ in range(n):
  a = I()
  cache[a] += 1
  for i in range(a-k, a+k+1):
    if i < 0 or i > 300001:
      continue
    cache[i] = max(cache[i], cache[a])

print(max(cache))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    alst = [int(input()) for _ in range(n)]
    N = 300010
    
    ll = - 10 ** 10    
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [ll]*(2*N0)
    
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v == ll:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = max(v, lazy[2*i-1], data[2*i-1], lazy[2*i], data[2*i])
            lazy[i-1] = ll
    
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
    
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = max(lazy[R-1], data[R-1], x)
            if L & 1:
                lazy[L-1] = data[L-1] = max(lazy[L-1], data[L-1], x)
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = max(data[2*i-1], data[2*i])
    
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r
    
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, data[R-1])
            if L & 1:
                s = max(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    ans = 0
    for a in alst:
        l = a - k
        r = a + k
        xx = query(a, a + 1) + 1
        update(l, r + 1, xx)
        ans = max(ans, xx)
    print(ans)
    
main()

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,2))
ans = 0
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        ans = max(ans,size)
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
        else:
            queue.append((r,size,i+1))
print(ans)

Submission status: Runtime Error

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

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in l[i + 1:]:
        if abs(i - j) <= k:
            num = max(num, root[j])
    root[i] += num
    if i < n - 1000:
        del l[-1]

print(max(root))

Submission status: Runtime Error

Solution code:
def dfs(start):
  global myList
  if start==n:
    return
  if len(myList) == 0:
    myList.append(a[start])
    dfs(start+1)
  else:
    if abs(myList[-1]-a[start])<=k:
      myList.append(a[start])
    dfs(start+1)  

n,k = map(int,input().split())
a = []
for i in range(n):
  a.append(int(input()))
#print(a)
ans = 0
for i in range(n):
  myList = []
  dfs(i)
  ans = max(ans,len(myList))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    alst = [int(input()) for _ in range(n)]
    N = max(alst) + 1
    
    
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [0]*(2*N0)
    
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v == 0:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = 0
    
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
    
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = max(lazy[R-1], data[R-1], x)
            if L & 1:
                lazy[L-1] = data[L-1] = max(lazy[R-1], data[L-1], x)
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = max(data[2*i-1], data[2*i])
    
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r
    
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, data[R-1])
            if L & 1:
                s = max(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    ans = 0
    for a in alst:
        l = a - k
        r = a + k
        x = query(a, a + 1) + 1
        update(l, r + 1, x)
        ans = max(ans, x)
    print(ans)
    
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

#####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


st = SegTree([0]*N, segfunc, ide_ele)
for _ in range(N):
    a = int(input())-1
    x = st.query(max(a-K, 0), min(a+K+1, N))
    st.update(a, x+1)

print(st.query(0, N))

Submission status: Runtime Error

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

l = 0
r = 1
while l < n:
    if l == r and r < n:
        r += 1
    if l == n-1:
        if abs(a[l]-b[-1]) <= k:
            b.append(a[l])
            break          
    if len(b) == 0:
        if abs(a[r]-a[l]) <= k:
            b.append(a[l])
            l = r
            continue
        r += 1
    else:
        if abs(a[l]-b[-1]) <= k and abs(a[r]-a[l]) <= k:
            b.append(a[l])
            l = r
            continue
        r += 1


print(len(b))

Submission status: Runtime Error

Solution code:
n,k = [int(x) for x in input().split()]
nums = []
absnums = []

for i in range(n):
      nums.append(int(input()))

#print(nums)

for i in range(len(nums)-1):
      if i == len(nums)-1:
            break
      
      if abs(nums[i]-nums[i+1]) > k:
            while(abs(nums[i] - nums[i+1]) > k):
                  del nums[i+1]
                  #print(nums)
            #absnums.append(abs(nums[i]-nums[i+1]))
      
print(len(nums))
#print(nums)
#print(absnums)

Submission status: Runtime Error

Solution code:
import sys
z=sys.stdin.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]*M)
for i in range(n):
    a=int(z())
    s[a]=1+s.query(a-k,a+k+1)
print(s.query(0,M))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = []
index = 0
for i in range(n):
    tmp = int(input())
    if i > 0:
        if abs(a[index-1] - tmp) > k:
            continue
    index += 1
    a.append(tmp)
    print(a)
print(len(a))

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 += 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
Tree=[0]*(N+1)
seg = SegTree(Tree, segfunc, ide_ele)
Ma=max(A)
ans=0
for i in range(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 = [int(x) for x in input().split()]
nums = []
absnums = []

for i in range(n):
      nums.append(int(input()))

#print(nums)

for i in range(len(nums)-1):
      if i == len(nums)-1:
            break
      
      if abs(nums[i]-nums[i+1]) <= k:
            absnums.append(abs(nums[i]-nums[i+1]))
      else:
            while(abs(nums[i] - nums[i+1]) > k):
                  del nums[i+1]
                  #print(nums)
            absnums.append(abs(nums[i]-nums[i+1]))
      
print(len(nums))

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l


if sys.platform =='ios':
	if input_method==input_methods[0]:
		ic=input_clipboard()
		input = lambda : ic.__next__()
	elif input_method==input_methods[1]:
		sys.stdin=open('inputFile.txt')
	else:
		pass
	isTest=True
else:
	pass
	#input = sys.stdin.readline

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
#num =2**(n-1).bit_length()
#seg=[ide_ele]*2*num


n, k = tin()
al = [int(input()) for _ in range(n)]
v_max = 300000
mmv = [0] * (v_max+1)
num=2**(v_max-1).bit_length()
seg = [ide_ele]*2*num
init(mmv)
for value_i in al:
	r = query(value_i-k, value_i+1+k)
	update(value_i, r-1)
v = -query(0, num)
print(v)

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())-1)

  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())

#####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


st = SegTree([0]*N, segfunc, ide_ele)
for _ in range(N):
    a = int(input())-1
    x = st.query(max(a-K, 0), min(a+K+1, N))
    st.update(a, x+1)

print(st.query(0, N))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 20
for i in range(N-1):
  tmp = 0
  for j in range(max(l[i]-3, 0), min(l[i]+4, 300000)):
    tmp = max(tmp, cnts[j])
  cnts[l[i]] = tmp+1
print(max(cnts))

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):
    print(current_value, i)
    if (current_value, i) in memo.keys():
        print('here')
        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))