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: Time Limit Exceeded

Solution code:
from math import ceil, log2
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

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

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        """
        最初はquery(a, b, 0, 0, self.num)で呼び出す
        [a:b) でクエリをよびだす
        @see https://www.slideshare.net/iwiwi/ss-3578491
        :param a:
        :param b:
        :param k: ノード
        :param l:
        :param r:
        :return:
        """
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
MAX_A = max(a)
st = SegTree([0]*MAX_A)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, MAX_A)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict


def update(heap, a, mode=1):
    while heap and abs(a - heap[0][0]) <= K:
        prev, length = heappop(heap)
        dp[a * mode] = max(dp[a * mode], length + 1)
    for key, value in dp.items():
        heappush(heap, (key * mode, value))


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
bigger = [(-A[0], -1)]
smaller = [(A[0], 1)]
for a in A[1:]:
    update(bigger, -a, -1)
    update(smaller, a)
print(max(dp.values()))

Submission status: Time Limit Exceeded

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

dp = [0] * (N + 1)
dp[1] = 1
m = 1
for i in range(2, N + 1):
    for j in reversed(range(1, i)):
        if abs(A[i] - A[j]) <= 3:
            if dp[j] == m:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])
                break
            else:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())

N,K=reads()
start,end=0,0
former=0
import math
maxval=0
ls=[]
sortls=[]
maxls=[1 for i in range(N)]
selectls=[0 for i in range(300000)]
for i in range(N):
    a=read()
    a-=1
    sls=selectls[a]
    maxls[i]=sls+1
    mi=max(0,a-K)
    ma=min(N-1,a+K)
    for l in range(mi,ma+1):
        selectls[l]=max(selectls[l],maxls[i])
print(max(maxls))

Submission status: Time Limit Exceeded

Solution code:
#D セグ木
n,K=map(int,input().split())
A= [int(input()) for _ in range(n)]

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

#####ide_ele#####
ide_ele = -1
#################

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

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

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

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

maxa=max(A)
z= [0 for i in range(maxa)]
seg = SegTree(z, segfunc, ide_ele)

for i in range(n):
    mini = max(0,A[i]-K)
    maxi = min(maxa,A[i]+K)
    tmp=seg.query(mini,maxi+1)
    seg.update(A[i],tmp+1)

print(seg.query(0,maxa+1))

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int,input().split())

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

ng = n+1
ok = 0

def queri(b):
    dp = list([0 for _ in range(b+1)] for _ in range(n+1)) 
    j = 0
    for i in range(n):
        la = dp[i][j]
        if abs(A[i]-la) <= k:
            dp[i+1][j+1] = A[i]
            j += 1
            if j == b:
                return True
        else:
            dp[i+1][j] = la

    if dp[-1][-1] != 0:
        return True
    else:
        return False

while ng - ok > 1:
    mid = (ok+ng)//2
    if queri(mid) :
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.min = float("inf")
        self.max = float("-inf")
        self.sum = float("inf")
        self.leftEdge = None
        self.rightEdge = None


class SegmentTree:
    def __init__(self):
        """
        Initializer method to initialize the class level objects
        :rtype: object
        """
        self.partial_overlap = "Partial overlap"
        self.no_overlap = "No overlap"
        self.complete_overlap = "Complete overlap"

    def get_overlap(self, x1, y1, x2, y2):
        """
        Method to get the overlapping type for a given ranges
        X1, Y1 -> Given node's range
        X2, Y2 -> Query range
        :return: type of overlap
        """
        if (x1 == x2 and y1 == y2) or (x1 >= x2 and y1 <= y2):
            overlap = self.complete_overlap
        elif (y1 < x2) or (x1 > y2):
            overlap = self.no_overlap
        else:
            overlap = self.partial_overlap
        return overlap

    def construct_segment_tree(self, array, start, end):
        """
        Method to construct a Segment tree using a given array elements
        :param end:
        :param start:
        :param array: Array elements
        :return: Root node of a segment tree
        """
        if end - start <= 0 or len(array) == 0:
            return None
        if end - start == 1:
            node = Node()
            node.min = array[start]
            node.max = array[start]
            node.sum = array[start]
            node.leftEdge = start
            node.rightEdge = end - 1
            return node
        else:
            node = Node()
            mid = start + (end - start) // 2
            node.left = self.construct_segment_tree(array, start=start, end=mid)
            node.right = self.construct_segment_tree(array, start=mid, end=end)
            if node.left is None and node.right is None:
                node.sum = 0
                node.leftEdge = start
                node.rightEdge = start
                node.min = float("inf")
                node.max = float("-inf")
            elif node.left is None:
                node.sum = node.right.sum
                node.leftEdge = node.right.leftEdge
                node.rightEdge = node.right.rightEdge
                node.min = node.right.min
                node.max = node.right.max
            elif node.right is None:
                node.sum = node.left.sum
                node.leftEdge = node.left.leftEdge
                node.rightEdge = node.left.rightEdge
                node.min = node.left.min
                node.max = node.left.max
            else:
                node.min = min(node.left.min, node.right.min)
                node.max = max(node.left.max, node.right.max)
                node.sum = node.left.sum + node.right.sum
                node.leftEdge = node.left.leftEdge
                node.rightEdge = node.right.rightEdge
            return node

    def update_segment_tree(self, head, index, new_value, array):
        """
        Method to update the segment tree node value
        :return: Head node of a segment tree
        :rtype: object
        """
        if index == head.leftEdge == head.rightEdge:
            head.max = new_value
            head.min = new_value
            head.sum = new_value
            array[index] = new_value
            return head
        elif (head.leftEdge <= index <= head.rightEdge) and (head.rightEdge > head.leftEdge):
            left_node = self.update_segment_tree(head=head.left, index=index, new_value=new_value, array=array)
            right_node = self.update_segment_tree(head=head.right, index=index, new_value=new_value, array=array)
            head.sum = right_node.sum + left_node.sum
            head.min = min(left_node.min, right_node.min)
            head.max = max(left_node.max, right_node.max)
            return head
        else:
            return head

    def get_minimum(self, head, left, right):
        """
        Method to get the minimum in a given range query
        :return: Minimum value for a given range query
        """
        overlap = self.get_overlap(head.leftEdge, head.rightEdge, left, right)
        if overlap == self.complete_overlap:
            return head.min
        elif overlap == self.no_overlap:
            return float("inf")
        elif overlap == self.partial_overlap:
            left_min = self.get_minimum(head=head.left, left=left, right=right)
            right_min = self.get_minimum(head=head.right, left=left, right=right)
            return min(left_min, right_min)

    def get_maximum(self, head, left, right):
        """
        Method to get the maximum value for a given range query
        :return Maximum value for a given range query
        """
        overlap = self.get_overlap(head.leftEdge, head.rightEdge, left, right)
        if overlap == self.complete_overlap:
            return head.max
        elif overlap == self.no_overlap:
            return float("-inf")
        elif overlap == self.partial_overlap:
            left_max = self.get_maximum(head=head.left, left=left, right=right)
            right_max = self.get_maximum(head=head.right, left=left, right=right)
            return max(left_max, right_max)

    def get_sum(self, head, left, right):
        """
        Method to return the sum of an array elements for a given range query
        :return: Returns the sum of an array elements for a given range query
        """
        overlap = self.get_overlap(head.leftEdge, head.rightEdge, left, right)
        if overlap == self.complete_overlap:
            return head.sum
        elif overlap == self.no_overlap:
            return 0
        elif overlap == self.partial_overlap:
            left_sum = self.get_sum(head=head.left, left=left, right=right)
            right_sum = self.get_sum(head=head.right, left=left, right=right)
            return left_sum + right_sum

    def preorder_traversal(self, head, array):
        if head is None:
            return
        print("Array = {} Min = {}, Max = {}, Sum = {}".format(array[head.leftEdge:head.rightEdge + 1], head.min,
                                                               head.max, head.sum))
        self.preorder_traversal(head=head.left, array=array)
        self.preorder_traversal(head=head.right, array=array)
        
'''
arr = [10, 20, 30, 40, 50, 60, 70]
st = SegmentTree()
root = st.construct_segment_tree(array=arr, start=0, end=len(arr))
left_index = 0
right_index = 4
update_index = 0
update_value = 200
print(st.get_sum(head=root, left=left_index, right=right_index))
print(st.get_minimum(head=root, left=left_index, right=right_index))
st.update_segment_tree(head=root, index=update_index, new_value=update_value, array=arr)
print(st.get_maximum(head=root, left=left_index, right=right_index))
st.preorder_traversal(root, arr)
'''

import sys
input = sys.stdin.readline
n,k = list(map(int, input().split()))
arr = []

for _ in range(n):
  x = int(input())
  arr.append(x)
  
zeros = [0] * (300001)
  
st = SegmentTree()
root = st.construct_segment_tree(array=zeros, start=0, end=len(zeros))

for el in arr:
  left_index = max(0, el-k)
  right_index = min(el+k,300000)
  best = st.get_maximum(head=root, left=left_index, right=right_index)
  #print(best)
  update_value = best + 1
  
  update_index = el 
  st.update_segment_tree(head=root, index=update_index, new_value=update_value, array=zeros)
  
  #update_index = el + k
  #st.update_segment_tree(head=root, index=update_index, new_value=update_value, array=zeros)
  
  #update_index = el - k
  #st.update_segment_tree(head=root, index=update_index, new_value=update_value, array=zeros)
  
best = st.get_maximum(head=root, left=0, right=300000)
print(best)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def main(n,k,a):
    t = [0 for i in range(2**20+1)]
    ans = 0
    for i in range(n):
        cur = a[i]
        floor = max(1,cur-k)
        ceil = min(cur+k,2**19)
        q = [1]
        temp = 1
        #print(cur,floor,ceil)
        while q:
            idx = q.pop(0)
            h = math.floor(math.log2(idx))
            curfloor = (idx-2**h) * 2**(19-h) + 1
            curceil = (idx-2**h+1) * 2**(19-h)
            nextceil = ((idx*2)-2**(h+1)+1) * 2**(19-(h+1))
            nextfloor = nextceil + 1
            #print(h,idx)
            #print(idx,curfloor,curceil,nextfloor,nextceil)
            if curfloor>=floor and curceil<=ceil:
                temp = max(temp,t[idx]+1)
                #print(idx,t[idx],curfloor,curceil)
            if nextceil>=floor and h<19:
                q.append(idx*2)
            if nextfloor<=ceil and h<19:
                q.append(idx*2+1)
            #t[idx] = max(t[idx],temp)
        idx = 1
        for h in range(20):
            t[idx] = max(t[idx],temp)
            idx *= 2
            nextceil = ((idx)-2**(h+1)+1) * 2**(19-(h+1))
            #print(nextceil)
            if cur>nextceil:
                idx += 1
    print(t[1])
        #print(t[2**19+2])
        

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [0 for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    
dp = [1 for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        if abs(A[i] - A[j]) <= K:
            dp[j] = max(dp[j], dp[i]+1)
print(max(dp))

Submission status: Time Limit Exceeded

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

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

print(max(dp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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())
    v,w=0,M
    if a>k:v=a-k
    if a+k+1<M:w=a+k+1
    s[a]=1+s.query(v,w)
print(s.query(0,M))

Submission status: Time Limit Exceeded

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

i_list = []
for i in range(N-1):
  for j in range(i+1,N):
    f = abs(A[j]-A[i])
    if f <= K:
      i_list.append([i,j])

cnt = 1
first = i_list[0][0]
F = A[first]
for i in range(first+1,N):
  num = abs(A[i]-F)
  if num <= K:
    F = A[i]
    cnt +=1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    A = [int(input()) for _ in range(n)]

    dp = [1] * n
    for i in range(1, n):
        cnt = 0
        for j in range(i):
            if abs(A[i] - A[j]) <= k:
                cnt = max(cnt, dp[j] + 1)
        dp[i] = cnt
    print(dp[-1])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
r = []
for x in a:
  r.append(max((z for y, z in zip(a, r) if abs(x - y) <= k), default=0) + 1)
print(max(r))

Submission status: Time Limit Exceeded

Solution code:

n, k = (int(x) for x in input().split())

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

# print(a_list)

ans = 0
b_list = []

# 開始地点を1つずつずらす
for j in range(n) :

    # print("■ 開始要素番号 : {0}".format(j))

    temp_ans = 0
    b = a_list[j]
    temp_b_list = []

    for i in range(j, n):
        
        # print("現在のBの末尾  : {0}".format(b))
        # print("対象の数 : {0}".format(a_list[i]))

        if abs(a_list[i] - b) <= k :

            # print("Bに追加!")

            temp_ans += 1
            b = a_list[i]
            temp_b_list.append(a_list[i])

    # print("作れた数列 : {0}".format(temp_b_list))
    # print("作れた数列の長さ : {0}".format(temp_ans))

    if ans < temp_ans :
        ans = temp_ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

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

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        """
        最初はquery(a, b, 0, 0, self.num)で呼び出す
        [a:b) でクエリをよびだす
        @see https://www.slideshare.net/iwiwi/ss-3578491
        :param a:
        :param b:
        :param k: ノード
        :param l:
        :param r:
        :return:
        """
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
MAX_A = max(a)
st = SegTree([0]*MAX_A)

for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, MAX_A)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
res = [st.query(i, i+1, 0, 0, st.num) for i in a]
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
s =[int(input())for i in range(a)]
w =[]
t =[]
for i in range(a):
    w.append(s[i])
    for j in range(i+1,a):
        if abs(w[-1] - s[j]) <=b:
            w.append(s[j]) 
    t.append(len(w))
    w.clear()
    if len(t) ==10:
        print(max(t))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(n):
  temp = [1]
  for j in range(i-1,-1,-1):
    if c[j] == 0:
      x = a[j]-a[i]
      if abs(x)<=3:
        temp.append(b[j]+1)
        c[j] = 1
  b[i] = max(temp)
print(max(b))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = []
t = []
l = -1

for i in range(n):
    b = int(input())
    a.append(b)

for i in range(n):
    cnt = 0
    if(l != a[i]):
        l = a[i]
        r = l
        for s in range(i,n):
            if((abs(a[s] - r)) <= k):
                cnt += 1
                r = a[s]
        t.append(cnt)

print(max(t))

Submission status: Time Limit Exceeded

Solution code:
from typing import List

A_MAX = 300000


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 = list(map(int, input().split()))
    A = [int(input()) for _ in range(N)]
    result = solve(A, K)
    print(result)


def solve(A: List[int], K: int) -> int:
    sg = SegTree([0] * (A_MAX + 1), lambda x, y: max(x, y), 0)
    for a in A:
        n = sg.query(max(0, a - K), min(A_MAX, a + K) + 1)
        sg.update(a, n + 1)
    return sg.query(0, A_MAX + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import types
import bisect
N , K = map(int,input().split())
A = [int(input()) for _ in range(N)]
Ad = set(A)
Ad = list(Ad)
length = len(Ad)
Ad.sort()
d = [0 for k in range(max(A)+1)]
candidate = [[] for i in range(length)]
Anum = [0]*(max(A)+1)
for i in range(length):
  j = Ad[i]
  Anum[j] = i
for i in range(length):
  ma = Ad[i]
  for j in range(i):
    target = Ad[i-j-1]
    if abs(target - ma) <= K:
      candidate[i].append(j)
    else:
      break
  for j in range(length - i):
    target = Ad[j+i]
    if abs(target - ma) <= K:
      candidate[i].append(j)
    else:
      break
for i in range(N):
  a = A[i]
  p = Anum[a]
  for j in candidate[p]:
    d[a] = max(d[a],d[Ad[j]]+1)
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = []
# N, K = 10, 3
# A = [1,5,4,3,8,6,9,7,2,4]
for _ in range(N):
  A.append(int(input()))
dp = [0]*N
nextdp = [1]*(300000)
tmp = 0
while tmp < N:
  dp[tmp] = nextdp[A[tmp]]
  for n in range(0,2*K+1):
    n -= K
    if 300000 > A[tmp]+n >= 0:
      nextdp[A[tmp]+n] = max(nextdp[A[tmp]+n], dp[tmp]+1)
  tmp += 1
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())
s =[int(input())for i in range(a)]
w =[]
t =[]
for i in range(a):
    w.append(s[i])
    for j in range(i+1,a):
        if abs(w[-1] - s[j]) <=b:
            w.append(s[j]) 
    t.append(len(w))
    w.clear()
print(max(t))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    b = [0]*(300010)
    dp = [0]*(n)
    for i in range(n):
        maxi = 0
        if len(b[max(0, a[i]-k):min(a[i]+k, n)]) != 0:
            maxi = max(b[max(0, a[i]-k):min(a[i]+k, n)+1])
        dp[i] = maxi + 1
        b[a[i]] = max(b[a[i]], dp[i])
    print(max(dp))
                
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

d1 = {} ;
for x in range ( N ) :
	a = int ( input().strip() ) ;
	d2 = {} ;
	
	for r in d1 :
		d = d2[r] if r in d2 else 0 ;
		d2 [ r ] = max ( d1[r]  , d ) ;

		if abs ( r -a )  > K : continue ;

		d = d2[a] if a in d2 else 0 ;
		d2 [ a ] = max ( d1[r] +1 , d ) ;

	d = d2[a] if a in d2 else 0 ;
	d2 [ a ] = max ( 0 +1 , d ) ;
	d1 = d2 ;
print ( max ( d1.values() ) ) ;