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:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()
# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16580070
class SegmentTree:
 
    __slots__ = ["func", "e", "original_size", "n", "data"]
 
    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
 
    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2
 
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)
 
    def all_folded(self):
        return self.data[1]
 
    def __getitem__(self, index):
        return self.data[self.n + index]
 
    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size
 
    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0

def main():
    n, k= map(int, input().split())
    A = 300010    
    st = SegmentTree(A,e=0)
    for _ in range(n):
        q = int(input())
        update=st.folded(max(0,q-k), min(300005,q+k+1))
        st.replace(q,update+1)
    print(st.all_folded())



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


class SegTree:
    X_unit = 0
    X_f = max

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

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

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

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

n,k = map(int,input().split())
seg = SegTree(300001)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.fold(0,300001))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000
num = 1 << ((max_n - 1).bit_length())
SEG = [0] * (2 * num)

func = max
ele = 0


def update(idx, val):
    idx += num
    SEG[idx] = val
    for i in reversed(range(1, num)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += num
    right += num
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


for _ in range(n):
    val = int(input())
    temp = query(max(0, val - k), min(max_n + 1, val + k + 1))
    temp += 1
    update(val, temp)


print(SEG[1])

Submission status: Time Limit Exceeded

Solution code:
# セグメントツリー
#############################################################

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

# val[i] = 最後の値がiである、最長の部分列の長さ
val = [0] * 300010
seg = SegTree(val, segfunc, ide_ele)
ans = 0

for i in range(N):
    a = int(input())
    # (a-K, a-K+1, ..., a+K-1, a+K の max) + 1 に更新する
    # 両端が範囲内に収まるように調整
    l = max(a - K, 0)
    r = min(a + K, 300000)
    # 半開区間
    tmp = seg.query(l, r + 1) + 1
    ans = max(ans, tmp)
    seg.update(a, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INT_MIN = 0

def init(n_):
    n = 1
    while n < n_:
        n *= 2
    dat = [INT_MIN] * (2*n-1)
    return n, dat

def update(k, a):
    k += n-1
    dat[k] = a
    while k > 0:
        k = (k-1) // 2
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INT_MIN
    if a <= l and r <= b:
        return dat[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
MAX_Ai = 3*10**5+1
n, dat = init(MAX_Ai)
for ai in A:
    max_len = query(max(ai-K, 0), min(ai+K+1, MAX_Ai), 0, 0, n)
    update(ai, max_len+1)
ans = query(0, MAX_Ai, 0, 0, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000
num = 1 << ((max_n - 1).bit_length())
SEG = [0] * (2 * num)

func = max
ele = 0


def update(idx, val):
    idx += num
    SEG[idx] = val
    for i in reversed(range(1, num)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += num
    right += num
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


for _ in range(n):
    val = int(input())
    # print("range", max(0, val - k), min(max_n + 1, val + k + 1) - 1)
    temp = query(max(0, val - k), min(max_n + 1, val + k + 1))
    # print(temp)
    temp += 1
    update(val, temp)
    # print(val, temp)
    # print(SEG[num : num + 12])

print(SEG[1])

Submission status: Time Limit Exceeded

Solution code:


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

rank[0]=1
for i in range(1,n):
    ap = a[i]
    r=0
    for j in range(i):
        if abs(a[j]-ap)<=k:
            r=max(r,rank[j])
    rank[i]=r+1
print(max(rank))

Submission status: Time Limit Exceeded

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

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

D=[0]*N
S=[0]*N

A=int(input())
D[0]=1
S[0]=A

for i in range(1,N):
    A=int(input())
    for j in range(i):
        if abs(S[j]-A)<=K:
            D[j]+=1
            S[j]=A
    D[i]=1
    S[i]=A

ans=max(D)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
l = [[int(input())]]
l_size = [1]
for i in range(n-1):
  a = int(input())
  max_size = 1
  max_tmp = [a]
  for j, item in enumerate(l):
    sa = item[-1] - a
    if sa <0:sa = -sa
    if sa <=k:
      tmp = item + [a]
      tmp_size = l_size[j]+1
      if max_size < tmp_size:
        max_size = tmp_size
        max_tmp = tmp
  l.append(max_tmp)
  l_size.append(max_size)
#  print(l)
  
ans = max(l_size)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
l = input().split(' ')
N = int(l[0])
K = int(l[1])
A = []
for i in range(N):
  A.append(int(input()))

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

for i in range(N):
  flg = False
  n = numpy.amax(dp)
  #print('a'+str(n))
  for j in range(n,-1,-1):
    arr = [k for k, x in enumerate(dp) if x == j]
    #print(arr)
    for k in range(len(arr)):
      if(abs(A[i]-A[arr[k]])<=K):
        dp[i] = dp[arr[k]]+1
        flg = True
        break
    if(flg):
      break

print(numpy.max(dp))

Submission status: Time Limit Exceeded

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

#####ide_ele#####
ide_ele = int(0)
#################

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

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

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

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

n, k = map(int, input().split())
a = [0]*300002

seg = SegTree(a, segfunc, ide_ele)
for _ in range(n):
    aa = int(input())

    m = seg.query(max(0,aa-k), min(aa+k,300000)+1)
    seg.update(aa, m+1)

print(seg.query(0, 300000))

Submission status: Time Limit Exceeded

Solution code:
"""
ACL0926_D
"""
import numpy as np

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
b=[0]*n 
c=[0]*n #差分メモ

b[0]=a[0]
a[0]=0

for i in range(1,n):
    for j in range(0,n-1):
        c[j]=abs(a[j]-b[i-1])
        if c[j]>k:
            c[j]=0
    max_index=np.argmax(c)
    b[i]=a[max_index]
    a[max_index]=0

for i in range(n):
    if b[i]==0:
        for j in range (i,n):
            b[j]=0
            
ans=np.count_nonzero(b)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(segt.query(0,300001))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2
import sys
z=sys.stdin.readline
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):
        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, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    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:
class SegmentTree:
    def __init__(self, a):
        self.padding = -float('inf')    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = max(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = max(self.seg_data[2*idx+1], self.seg_data[2*idx+2])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = max(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = max(result, self.seg_data[idx2])
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
A = 300001
st = SegmentTree([0]*A)

for i in range(N):
    a = int(input())
    l = max(0, a-K)
    r = min(A-1, a+K)
    max_len = st.query(l, r+1)
    st.update(a, max_len+1)

print(st.query(1, A))

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):
        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)]
M=300001
st = SegTree([0]*M)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    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:
class SegmentTree():

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

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

def main():
    n,k = tuple([int(t)for t in input().split()])
    size = 3*10**5
    lst = SegmentTree(size+1)
    for _ in range(n):
        a = int(input())
        l,r = max(a-k,0),min(a+k+1,size+1)
        m = min(lst.query(l,r),0)
        lst.update(a,m-1)

    print(-lst.query(0,3*10**5))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-n), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

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

    def max_right(self, l, x):
        """[l,r) が ok であるような最大の r を返す"""
        if l == self.n:
            return l
        l += self.size
        res = self.sta
        check = True
        while check or (l & -l) != l:
            check = False
            while l%2 == 0:
                l >>= 1
            if not self.func(res,self.tree[l]) < x:
                while l < self.size:
                    l <<= 1
                    if self.func(res,self.tree[l]) < x:
                        res = self.func(res,self.tree[l])
                        l += 1
                return l - self.size
            res = self.func(res,self.tree[l])
            l += 1
        return self.n

    def min_left(self, r, x):
        """(r が ok であるような最小の r を返す probably wrong"""
        if r == 0:
            return 0
        r += self.size
        res = self.sta
        check = True
        while check and (r & -r) != r:
            check = False
            r -= 1
            while (r > 1 and r%2):
                r >>= 1
            if not self.func(res, self.tree[r]) < x:
                while r < self.size:
                    r = 2*r + 1
                    if self.func(res, self.tree[r]) < x:
                        res = self.func(res, self.tree[r])
                        r -= 1
                return r + 1 - self.size
            res = self.func(self.tree[r],res)
        return 0


n,k = map(int,input().split())
M = 3*10**5+5
tree = SegTree(M,max,0)
for i in range(n):
    a = int(input())
    x = tree.get(max(0,a-k),min(a+k+1,M))
    tree.set(a,x+1)

print(tree.get(0,M))

Submission status: Time Limit Exceeded

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

BL = (300000).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH

# TODO: default value
buf = [0] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(q_left, q_right):
    return _search(0, WIDTH, 0, q_left, q_right)

def _search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return 0
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

def compare(i1, i2):
    if i1 > i2:
        return i1
    else:
        return i2

for _ in range(N):
    a = int(input())
    maxlen = search(a-K, a+K)
    update(a, maxlen+1)
print(search(0, 300000))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

N, K = list(map(int, input().split()))
A = [0] * N
landmark = [1] * N
for i in range(N):
    A[i] = int(input())

queue = deque()
for i in range(N - 1):
    queue.append([[i], i + 1])
while len(queue) != 0:
    now, ind = queue.popleft()
    # 探索条件
    if ind >= N:
        break
    # print("now", now, ind)
    if landmark[ind] <= len(now):
        while True:
            if ind >= N:
                break
            if abs(A[ind] - A[now[-1]]) <= K and landmark[ind] < len(now) + 1:
                queue.appendleft([copy.copy(now), ind + 1])
                now.append(ind)
                queue.appendleft([copy.copy(now), ind + 1])
                landmark[ind] = len(now)
                break
            else:
                ind += 1
print(max(landmark))

Submission status: Time Limit Exceeded

Solution code:
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)

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
M=1048576
s=SegmentTree([0]*M)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(max(a-k,0),a+k+1)
print(s.query(0,M))

Submission status: Time Limit Exceeded

Solution code:

n,k=map(int,input().split())

s=[1]*n
t=[[] for i in range(n+1)]
a=[0]*n
for i in range(n):
    a[i]=int(input())
    ast=max(a[i]-k,0)
    aed=min(a[i]+k,n)
    for ai in range(ast,aed+1):
        t[ai].append(i)
    
for i in range(n):
    for ti in t[a[i]]:
        if ti<i:
            s[i]=max(s[i],s[ti]+1)
            
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-09-26 22:28:46 +0900
# LastModified: 2020-09-26 22:41:30 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from copy import deepcopy


def main():
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(int(input()))
    ans = 0
    for i in range(N):
        cnt = 0
        unko = [A[i]]
        j = 1
        while j < len(A):
            if abs(unko[-1]-A[j]) <= K:
                unko.append(A[j])
                cnt += 1
            j += 1
        if cnt > ans:
            ans = cnt
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
M=600001
s=SegmentTree([0]*M)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(max(a-k,0),a+k+1)
print(s.query(0,M))

Submission status: Time Limit Exceeded

Solution code:
"""
ACL0926_D
"""
import numpy as np

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

b[0]=a[0]
a[0]=0

for i in range(1,n):
    for j in range(0,n-1):
        c[j]=abs(a[j]-b[i-1])
        if c[j]>k:
            c[j]=0
    max_index=np.argmax(c)
    b[i]=a[max_index]
    a[max_index]=0

for i in range(n):
    if b[i]==0:
        for j in range (i,j):
            b[j]=0
            
ans=np.count_nonzero(b)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N, K = map(int, input().split())
    A = np.array([int(input()) for _ in range(N)])
    dpn = np.array([1 for _ in range(N)])
    for i in range(N):
        I = np.where(np.abs(A-A[i]) <= K)
        I = I[0][I[0]>i]
        dpn[I] = np.maximum(dpn[I], dpn[i]+1)
                    
    return max(dpn)


if __name__ == '__main__':
    print(solve())