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:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
m = 0
for i in range(n-1):
    j = i
    l = i + 1
    count = 1
    while l < n:
        if abs(a[j] - a[l]) <= k:
            count += 1
            j = l
            l += 1
        else:
            l += 1
    m = max(m, count)

print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K, *A = map(int, open(0).read().split())

A = [a + 1 for a in A]
M = max(A)

N0 = 2 ** (M - 1).bit_length()
data = [0] * (2 * N0)

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

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 a in A:
    x = query(max(1, a - K), min(a + K + 1, M + 1))
    update(a, x + 1)

print(query(1, M))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int , raw_input().split())
ais = [int(raw_input()) for _ in range(n)]
h = [0 for oo in range(300001)]
for ai in ais:
    h[ai]  = 1 + max([h[v] for v in range(ai-k, ai + k +1) if 0<=v<len(h)] or [0])
print max(h)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def segfunc(x, y):
    # 求めたい値を算出するためのロジックを書く
    return max(x, y)


class SegmentTree:
    # ide_ele は単位元。初期値
    def __init__(self, init_val, ide_ele):
        self.n = len(init_val)
        self.ide_ele = ide_ele
        self.num = 2 ** (self.n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(self.n):
            self.seg[i + self.num - 1] = init_val[i]

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

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

    # 0-indexed
    # 半開区間 pからq - 1 までが担当範囲
    # [p, q)
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, self.seg[p])
        else:
            res = segfunc(segfunc(res, self.seg[p]), self.seg[q])
        return res


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

    init_val = [0] * 300002
    s = SegmentTree(init_val, 0)

    ma = max(A)
    for a in A:
        ans = s.query(max(0, a - K), min(ma, a + K) + 1)
        s.update(a, ans + 1)
    print(s.query(0, ma + 1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ans = 0
dp_max = 3*(10**5)+5
dp = [0] * dp_max
for i in range(n):
    ai = int(input())
    longest = 0
    for aj in range(max(0, ai-k), min(ai+k+1, dp_max)):
        longest = max(longest, dp[aj])
    dp[ai] = max(dp[ai], longest + 1)
    ans = max(ans, dp[ai])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree(object):

    def __init__(self, length, op=min, e=lambda: 0):
        """
        :param length: length of initial values
        :param op: operator, op(x, y) -> z
        :param e: function that return identity element for op
        """
        self.op = op
        self.e = e
        self.n = 1
        while self.n < length:
            self.n *= 2  # pow2
        self.dat = [e()] * (2 * self.n - 1)

    def initialize(self, x_list):
        """
        initialize data
        :param x_list: initial values fot list
        :return:
        """
        assert len(x_list) <= self.n
        # update base
        # ith -> n - 1 + i
        for i, x in enumerate(x_list):
            self.dat[self.n - 1 + i] = x
        # upper values
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.op(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        """
        update k-th(0-indexed) value with a
        :param k: index to set(0-indexed)
        :param a: value to set
        :return: None
        """
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2  # parent
            self.dat[k] = self.op(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        """
        :param p: int
        :param q: int
        :return: "minimum" value in [p, q)
        """
        if q <= p:
            return self.e()
        p += self.n - 1
        q += self.n - 2
        res = self.e()

        while q - p > 1:
            if p & 1 == 0:
                res = self.op(res, self.dat[p])
            if q & 1 == 1:
                res = self.op(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.op(res, self.dat[p])
        else:
            res = self.op(self.op(res, self.dat[p]), self.dat[q])
        return res

    def query_recursive(self, p, q):
        """
        recursive version, Ref. Ant Book p.155
        :param p: int
        :param q: int
        :return: "minimum" value in [p, q)
        """
        if q <= p:
            return self.e()
        return self._query_recursive(p, q, 0, 0, self.n)

    def _query_recursive(self, a, b, k, l, r):
        """
        :param a: int
        :param b: int
        :param k: int
        :param l: int
        :param r: int
        :return: "minimum" value in [a, b) and [l, r)
        """
        # no intersection -> e
        if r <= a or b <= l:
            return self.e()
        # [a, b) includes [l, r) -> return [l, r)
        if a <= l and r <= b:
            return self.dat[k]
        else:
            # ask children
            vl = self._query_recursive(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self._query_recursive(a, b, k * 2 + 2, (l + r) // 2, r)
        return self.op(vl, vr)


def solve(n, k, a_list):
    seg_tree = SegmentTree(300001, max, e=lambda: 0)
    for i in range(n):
        a = a_list[i]
        r = seg_tree.query(max(0, a - k), min(a + k + 1, 300001))
        seg_tree.update(a, r + 1)
    return seg_tree.query(0, 300001)


def main():
    n, k = map(int, input().split())
    a_list = [int(input()) for _ in range(n)]
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(10, 3, [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]) == 7


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

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

def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


def build(raw_data):
    N = len(raw_data)
    seg = np.empty(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg
 

def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 

def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 

def max_right(seg, l, x):
    """[l,r) が ok であるような最大の r を返す"""
    N = len(seg) // 2
 
    def is_ok(v):
        return v < x
 
    v = None
    i, node_l, node_w = l + N, l, 1
    while True:
        if not (i & 1):
            i >>= 1
            node_w <<= 1
            continue
        if node_l + node_w > N:
            break
        v1 = seg_f(v, seg[i])
        if is_ok(v1):
            v, i = v1, (i + 1) >> 1
            node_l, node_w = node_l + node_w, node_w << 1
        else:
            break
    # 奇数セルに居て、とりきれないことが分かっている。偶数をとっていく
    i, node_w = i << 1, node_w >> 1
    while node_w:
        if node_l + node_w > N:
            i, node_w = i << 1, node_w >> 1
            continue
        v1 = seg_f(v, seg[i])
        if is_ok(v1):
            v, i = v1, (i + 1) << 1
            node_l, node_w = node_l + node_w, node_w >> 1
        else:
            i, node_w = i << 1, node_w >> 1
    i >>= 1
    return i - N


def main(K, A):
    MAX = 300_010
    seg = np.zeros(2 * MAX, np.int64)
    for x in A:
        l, r = max(0, x - K), min(MAX, x + K + 1)
        n = fold(seg, l, r) + 1
        set_val(seg, x, n)
    return fold(seg, 0, MAX)
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
print(main(K, A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N, K = MI()
    A = []
    max_a = 0
    for i in range(N):
        a = II()
        A.append(a)
        max_a = max(max_a, a)

    dp = [0] * N
    last_index = [-1] * (max_a + 1)

    for i in range(N):
        pres = []
        target = A[i]
        for k in range(target-K, target+K+1):
            if k < 0 or k > max_a:
                continue
            if last_index[k] == -1:
                pres.append(1)
                continue
            pres.append(dp[last_index[k]] + 1)
        dp[i] = max(pres)
        last_index[target] = i

    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

D=20
S=[]
for i in range(D):
    S.append([0]*300010)

for i in range(N):
    A=int(input())
    R=min(A+K,300000)
    L=max(A-K,0)

    C=0
    for j in range(D):
        if L>R: break

        if L==R:
            C=max(C,S[j][L])
            break 

        if R%2==0:
            C=max(C,S[j][R])
            R=R//2-1
        else:
            R=R//2

        if L%2==1:
            C=max(C,S[j][L])
            L=L//2+1
        else:
            L=L//2
        
    S[0][A]=C+1
    for j in range(1,D):
        a=A//2
        B=A+1-2*(A%2)
        S[j][a]=max(S[j-1][A],S[j-1][B])
        A=a
    
ans=S[D-1][0]    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys  import stdin,stdout

from collections import Counter

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

from bisect import bisect_left,bisect_right

mod=1000000007
INF=float('inf')
                
def solve():
    n,k=mp()
    l=[inp() for i in range(n)]
    dp=[1 for i in range(n)]
    for i in range(1,n):
        for j in range(i):
            
            if abs(l[i]-l[j])<=k:
                dp[i]=max(dp[i],1+dp[j])
       
    pr(dp[-1])
            

    
for _ in range(1):

    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

D=20
S=[]
for i in range(D):
    S.append([0]*300010)

ans=0
for i in range(N):
    A=int(input())
    R=min(A+K,300000)
    L=max(A-K,0)

    C=0
    for j in range(D):
        if L>R: break

        if L==R:
            C=max(C,S[j][L])
            break 

        if R%2==0:
            C=max(C,S[j][R])
            R=R//2-1
        else:
            R=R//2

        if L%2==1:
            C=max(C,S[j][L])
            L=L//2+1
        else:
            L=L//2
        
    tmp=C+1
    ans=max(tmp,ans)

    S[0][A]=tmp
    for j in range(1,D):
        a=A//2
        if A%2==0:
            B=A+1
        else:
            B=A-1
        S[j][a]=max(S[j-1][A],S[j-1][B])
        A=a
    
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

S=[]
for i in range(19):
    #S.append([0]*2**i)
    S.append([0]*300010)
S.append([0]*300010)

ans=0
for i in range(N):
    A=int(input())
    R=min(A+K,300000)
    L=max(A-K,0)

    #tmp=max(S[19][L:(R+1)])+1
    #M=[]
    j=19
    C=0
    while(1):
        if L>R: break

        if L==R:
            #.append(S[j][L])
            C=max(C,S[j][L])
            break 

        if R%2==0:
            C=max(C,S[j][R])
            R=R//2-1
        else:
            R=R//2

        if L%2==1:
            C=max(C,S[j][L])
            L=L//2+1
        else:
            L=L//2

        j-=1
        if j<0: break
        
    tmp=C+1
    ans=max(tmp,ans)

    #S[A]=tmp
    S[19][A]=tmp
    for j in range(18,-1,-1):
        a=A//2
        if A%2==0:
            B=A+1
        else:
            B=A-1
        S[j][a]=max(S[j+1][A],S[j+1][B])
        A=a
    
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説などを参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

class SegTree:
    # 参考
    # https://algo-logic.info/segment-tree/#toc_id_1
    # https://qiita.com/takayg1/items/c811bd07c21923d7ec69
    def __init__(self, elm, func, default):
        # create val
        self.layer = ((len(elm) - 1) << 1).bit_length()
        self.num = 1 << (len(elm) - 1).bit_length()
        self.func = func
        # self.tree = [default] * (2 ** self.layer - 1)
        self.tree = [default] * 2 * self.num
        self.default = default
        # update leaf
        for i in range(len(elm)):
            self.tree[self.num + i] = elm[i]
        # update nodes
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

    def update(self, i, x):
        i = self.num + i
        self.tree[i] = x
        while i > 1:
            i = i // 2
            self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

    def query(self, l, r):
        return self.__query(l, r, 1, 0, self.num)

    def __query(self, l, r, k, ll, rr):
        re = self.default
        if rr <= l or r <= ll:
            return re
        if l <= ll and rr <= r:
            return self.tree[k]
        vl = self.__query(l, r, k * 2, ll, ll + (rr - ll) // 2)
        rl = self.__query(l, r, k * 2 + 1, ll + (rr - ll) // 2, rr)
        return self.func(vl, rl)


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, A):
    import math
    dp = [0] * (max(A) + 1)
    st = SegTree(dp, lambda x, y: max(x, y), -(math.inf))
    for a in A:
        # print(st.query(a - K, a + K + 1))
        st.update(a, st.query(a - K, a + K + 1) + 1)
    print(st.query(0, max(A) + 1))


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    solve(N, K, A)

    # # test
    # from random import randint
    # from func import random_str
    # 
    # N, K = 300000, 300000
    # A = [i for i in range(1, N + 1)]
    # print(N, K)
    # print(A)
    # print()
    # solve(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
# 解説などを参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

class SegTree:
    # 参考
    # https://algo-logic.info/segment-tree/#toc_id_1
    # https://qiita.com/takayg1/items/c811bd07c21923d7ec69
    def __init__(self, elm, func, default):
        # create val
        self.layer = ((len(elm) - 1) << 1).bit_length()
        self.func = func
        self.tree = [default] * (2 ** self.layer - 1)
        self.default = default
        # update leaf
        for i in range(len(elm)):
            self.tree[2 ** (self.layer - 1) - 1 + i] = elm[i]
        # update nodes
        for i in reversed(range(2 ** (self.layer - 1) - 1)):
            self.tree[i] = self.func(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    def update(self, i, x):
        i = 2 ** (self.layer - 1) - 1 + i
        self.tree[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.tree[i] = self.func(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    def query(self, l, r):
        return self.__query(l, r, 0, 0, 2 ** (self.layer - 1))

    def __query(self, l, r, k, ll, rr):
        re = self.default
        if rr <= l or r <= ll:
            return re
        if l <= ll and rr <= r:
            return self.tree[k]
        vl = self.__query(l, r, k * 2 + 1, ll, ll + (rr - ll) // 2)
        rl = self.__query(l, r, k * 2 + 2, ll + (rr - ll) // 2, rr)
        return self.func(vl, rl)


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, A):
    import math
    dp = [0] * (max(A) + 1)
    st = SegTree(dp, lambda x, y: max(x, y), -(math.inf))
    for a in A:
        # print(st.query(a - K, a + K + 1))
        st.update(a, st.query(a - K, a + K + 1) + 1)
    print(st.query(0, max(A) + 1))


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    solve(N, K, A)

    # # test
    # from random import randint
    # from func import random_str
    #
    # N, K = 300000, 300000
    # A = [i for i in range(1, N + 1)]
    # print(N, K)
    # print(A)
    # print()
    # solve(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300001,[0]*300001)
ans = 1
for i in range(N):
  A = int(input())
  l,r = max(0,A-K),min(A+K,300000)
  v = ST.prod(l,r+1)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

S=[0]*300010

ans=0
for i in range(N):
    A=int(input())
    R=min(A+K,300000)
    L=max(A-K,0)

    tmp=max(S[L:(R+1)])+1
    ans=max(tmp,ans)
    S[A]=tmp
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
class segtree:
  def __init__(self,n,operator,identity):
    nb = bin(n)[2:]
    bc = sum([int(digit) for digit in nb])
    if bc == 1:
      self.num_end_leaves = 2**(len(nb)-1)
    else:
      self.num_end_leaves = 2**(len(nb))
    self.array = [identity for i in range(self.num_end_leaves*2)]
    self.identity = identity
    self.operator = operator
  def update(self,x,val):
    actual_x = x+self.num_end_leaves
    self.array[actual_x] = val
    while actual_x > 0:
      actual_x = actual_x//2
      self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])
  def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
    width_of_floor = self.num_end_leaves//(2**depth) 
    leaf_right = leaf_left+width_of_floor-1 
    if leaf_left > q_right or leaf_right < q_left:
      return  self.identity 
    elif leaf_left >= q_left and leaf_right <= q_right:
      return self.array[arr_ind] 
    else: 
      val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
      val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
      return self.operator(val_l,val_r)     
def mx(x,y):
  return max(x,y)
dp = segtree(300005,mx,0)
for i in range(n):
  ai = int(input())
  l = max(0,ai-k)
  r = min(300005,ai+k)
  now = dp.get(l,r) + 1
  dp.update(ai,now)
print(dp.get(1,300005))

Submission status: Time Limit Exceeded

Solution code:
n, k, *al = map(int, open(0).read().split())
d = [0] * 300001
for a in al:
    l = max(0, a-k)
    r = min(a+k, 300000)
    m = 0
    for i in range(l, r+1):
        m = max(m, d[i])
    d[a] = max(d[a], m+1)
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
class segtree:
    """
    segment tree
    value store as object type and get update function(merge_func) from outside

    Attributes
    ----------
    n : int
        Number of elements
    initialize_func : func
        function for initialization
    merge_func : func
        function for merge x and y to x(this merge is distruction update)

    Methods
    -------
    update(i, x)
        update tree[i] value to x
    get(a, b)
        get value from [a, b)
        include a but not include b, return a merged value
    """
    def __init__(self, n, initialize_func, merge_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        initialize_func : func
            function for initialization
        merge_func : func
            function for merge x and y to x(this merge is distruction update)
        """
        self.n = n
        self.initialize = initialize_func
        self.merge = merge_func
        n2 = 1  # n2はnより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [initialize_func() for _ in range(n2 << 1)]

    def update(self, index, x):
        index += self.n2
        self.tree[index] = self.merge(self.tree[index], x)
        while index > 1:
            # (index ^ 1) はiと1の排他的論理和(XOR)
            x = self.merge(x, self.tree[index ^ 1])
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            self.tree[index] = self.merge(self.tree[index], x)

    def get(self, a, b):
        result = self.initialize()
        q = [(1, 0, self.n2)]
        while q:
            k, left, right = q.pop()
            if a <= left and right <= b:
                result = self.merge(result, self.tree[k])
                continue
            m = (left + right) // 2
            k <<= 1
            if a < m and left < b:
                q.append((k, left, m))
            if a < right and left < m:
                q.append((k + 1, m, right))
        return result


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    max_A = 3 * 10 ** 5 + 1

    seg = segtree(max_A, lambda: 0, max)
    for a in A:
        next = seg.get(max(0, a - K), min(a + K + 1, max_A))
        seg.update(a, next + 1)
    print(seg.get(0, max_A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 1-index
def segfunc(x, y):
    return max(x, y)

ide_ele = 0

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):
        """
        [l, r)のsegfuncしたものを得る
        """
        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())
T = []
for i in range(N):
    a = int(input())
    T.append(a)

A = [0]*(max(T)+1)
s_tree = segtree(A, segfunc, ide_ele)
for i in range(N):
    a = T[i]
    p = s_tree.query(max(a - K, 0), min(a + K + 1, max(T)+1))
    s_tree.update(a, p + 1)

print(s_tree.query(0, max(T)+1))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  for j,Aj in enumerate(As):
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

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

MAX = 300001

segt = SegTree([0] * MAX, lambda x, y: max(x, y), 0)
for a in A:
    l = max(0, a - k)
    r = min(MAX, a + k + 1)
    m = segt.query(l, r)
    segt.update(a, m + 1)

print(segt.query(0, MAX))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    idEle = -INF  # max
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


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

    maxA = max(As)

    data, numPow2 = makeSegTree(maxA+1)
    setInit([0]*(maxA+1))

    for A in As:
        L, R = A-K, A+K
        if L < 0:
            L = 0
        if R > maxA:
            R = maxA
        v = getValue(L, R+1)
        update(A, v+1)

    ans = getValue(0, maxA+1)
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
line = input().rstrip().split(" ")
num = int(line[0])
diffirence = int(line[1])

digitline = []
for i in range(num):
        digitline.append(int(input().rstrip()))

answer = 0
for j in range(num // 2):
    lastdigit = digitline[j]
    answerlist = [lastdigit]
    for k in range(num - j):
        digit = digitline[j + k]
        if abs(digit - lastdigit) <= diffirence:
            answerlist.append(digit)
            lastdigit = digit
    if answer <= len(answerlist):
        answer = len(answerlist)
    if answer >= (num - j - 1):
        break

print(answer - 1)

Submission status: Time Limit Exceeded

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

l[0].append(a[0])
ans=0
for ai in a[1:]:
  for i in reversed(range(ans+1)): # if can a_i put backword, add l[i+1]. because of maximum length answer 
    for li in l[i]:
      if -k<=(li-ai)<=k:
        ans=max(ans,i+1)
        l[i+1].append(ai)
        break
    else:
      continue
    break
  else:
    l[0].append(ai)

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
line = input().rstrip().split(" ")
num = int(line[0])
diffirence = int(line[1])

digitline = []
for i in range(num):
        digitline.append(int(input().rstrip()))

answer = 0
for j in range(num // 2):
    lastdigit = digitline[j]
    answerlist = [lastdigit]
    for k in range(num - j):
        digit = digitline[j + k]
        if abs(digit - lastdigit) <= diffirence:
            answerlist.append(digit)
            lastdigit = digit
    if answer <= len(answerlist):
        answer = len(answerlist)

print(answer - 1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=[]
for i in range(n):
  arr.append(int(input()))
 
dp=[0 for i in range(n)]
dp[0]=1
for i in range(1,n):
    
    for j in range(i):
        if abs(arr[j]-arr[i])<=k:
            dp[i]=max(dp[i],dp[j])
    dp[i]+=1
print(dp[n-1])