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:
def op(a,b):
    return max(a,b)

class segmentTree:
    def __init__(self,n,op,init_value):
        dataLen=1 << (n - 1).bit_length()
        self.data=[init_value]*(2*dataLen)
        self.op=op
        self.length=dataLen
    def getIdx(self,left,right):
        idxs=[]
        l=left
        r=right
        while True:
            idx=1
            valueL=0
            valueR=self.length-1
            while l!=valueL or valueR>=r:
                if l<=valueL+(valueR-valueL)//2:
                    valueR-=(valueR-valueL+1)//2
                    idx*=2
                else:
                    valueL+=(valueR-valueL+1)//2
                    idx=idx*2+1
            idxs.append(idx)
            if valueR==r or valueR==r-1 :
                break
            l=valueR+1
        return idxs
    def get(self,n):
        return self.data[self.getIdx(n,n+1)[0]]

    def set(self,n,value):
        idx1=self.getIdx(n,n+1)[0]
        self.data[idx1]=value
        while idx1!=1:
            idx2=idx1^1
            if idx1>idx2:
                idx1,idx2=idx2,idx1
            self.data[idx1//2]=self.op(self.data[idx1],self.data[idx2])
            idx1//=2
    def query(self,l,r):
        idxs=self.getIdx(l,r)
        ret=self.data[idxs[0]]
        for idx in idxs:
            ret=self.op(ret,self.data[idx])
        return ret


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


seg = segmentTree(N, op, 0)

for i in A:
  l=min(N,max(0,i-K))
  r=max(0,min(N,i+K))
  v=seg.query(l,r+1)
  seg.set(i,v+1)
print(seg.query(0,N))

Submission status: Time Limit Exceeded

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

#####ide_ele#####
ide_ele = 0
#################

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

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

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

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

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
dp=[0]*(300030)
seg=SegTree(dp,segfunc,ide_ele)
for x in a:
    l=max(0,x-k)
    r=min(x+k,300005)
    dp[x]=seg.query(l,r+1)+1
    seg.update(x,dp[x])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")
 
 
# update: node[x] を更新する
# getmin: 区間 [a, b) の最小値を返す
class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 1
        while n < size:
            n *= 2
        self.n = n
        self.node = [0]*(2*n - 1)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = max(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
    
    def getmax(self, a, b, k=0, l=0, r=-1):
        if r < 0:
            r = self.n
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.node[k]
        
        vl = self.getmax(a, b, 2*k+1, l, (l+r)//2)
        vr = self.getmax(a, b, 2*k+2, (l+r)//2, r)
        return max(vl, vr)
 
 
# 処理内容
def main():
    N, K = map(int, input().split())
    
    seg = SegmentTree([0]*300010)
    ans = 0
    for _ in range(N):
        A = int(input())
        a = max(A-K, 0)
        b = min(A+K, 300000)
        tmp = seg.getmax(a, b+1) + 1
        ans = max(ans, tmp)
        seg.update(A, tmp)
    
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__bit_code = """
def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_segtree_code = """
import typing

# import atcoder._bit


class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = atcoder._bit._ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
"""

atcoder.segtree = types.ModuleType('atcoder.segtree')
atcoder.segtree.__dict__['atcoder'] = atcoder
atcoder.segtree.__dict__['atcoder._bit'] = atcoder._bit
exec(_atcoder_segtree_code, atcoder.segtree.__dict__)
SegTree = atcoder.segtree.SegTree

#!/usr/bin/env python3

# from atcoder.segtree import SegTree
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

op = max
e = 0

dp = SegTree(op, e, 300005)

for i in range(N):
    x = A[i]
    now = dp.prod(max(x - K, 0), min(x + K + 1, 300005)) + 1
    dp.set(x, now)

ans = dp.prod(0, 300005)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


class SegTree:
    """
    Segment Tree
    """

    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] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新 O(N)

        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したものを得る O(logN)

        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

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


def main():
    N, K = map(int, input().split())
    A = []
    MAX = 300005
    for i in range(N):
        A.append(int(input()))

    ide_ele = 0

    dp = SegTree([0] * MAX, segfunc=max, ide_ele=ide_ele)

    for i in range(N):
        a = A[i]
        l = max(0, a - K)
        r = min(MAX, a + K + 1)
        now = dp.query(l, r) + 1
        dp.update(a, now)

    print(dp.query(0, MAX))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def init(init_val):
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
    
n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
#n = int(input())
#a = tuple(map(int,input().split()))

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

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

ans = 0

for i in range(n):
    tmp = query(max(0,a[i]-k),min(a[i]+k+1,max(a)+1))
    #print(i,a[i],max(0,a[i]-k),min(a[i]+k,max(a)))
    update(a[i],tmp+1)
    #print(tmp)
    #print(st.query(0, max(a)))
    #ans = max(ans,tmp+1)
    #print(seg[0],k)
#print(seg)
#print(query(0,max(a)),seg[0])
print(seg[0])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


# update: node[x] を更新する
# getmin: 区間 [a, b) の最小値を返す
class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 1
        while n < size:
            n *= 2
        self.n = n
        self.node = [0]*(2*n - 1)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = max(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
    
    def getmax(self, a, b, k=0, l=0, r=-1):
        if r < 0:
            r = self.n
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.node[k]
        
        vl = self.getmax(a, b, 2*k+1, l, (l+r)//2)
        vr = self.getmax(a, b, 2*k+2, (l+r)//2, r)
        return max(vl, vr)


# 処理内容
def main():
    N, K = map(int, input().split())
    
    seg = SegmentTree([0]*300010)
    ans = 0
    for _ in range(N):
        A = int(input())
        a = max(A-K, 0)
        b = min(A+K, 300000)
        tmp = seg.getmax(a, b+1) + 1
        ans = max(ans, tmp)
        seg.update(A, tmp)
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

idx=0
for ai in a:
  for i in range(idx+1):
    if len(subs[i])==0:
      subs[i].append(ai)
      idx+=1
      break
    else:
      if abs(subs[i][-1]-ai)<=k:
        subs[i].append(ai)

ans=0
for i in range(idx):
  #print(subs[i])
  ans=max(ans,len(subs[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  # return idx-value
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return max(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret

def run():
    N, K, *A = mapread()
    alim = max(A)
    st = segtree(alim+1, init = 0)

    for a in A:
        v = st.eval(max(0, a- K), min(alim, a + K))
        st.update(a, v + 1, by = False)

    print(st.bins[1])

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.dp = [0 for _ in range(2 * n)]
        
    def update(self, k, a):
        k += self.n
        self.dp[k] = a
        while (k > 1):
            self.dp[k >> 1] = max(self.dp[k], self.dp[k ^ 1])
            k >>= 1
        
    def query(self, l, r):
        res = 0
        l, r = l + self.n, r + self.n
        while l < r:
            if l & 1:
                res = max(res, self.dp[l])
                l += 1
            if r & 1:
                res = max(res, self.dp[r - 1])
            l, r = l >> 1, r >> 1
        return res
    
    
n, k = map(int, input().split())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
num = max(A) + k + 1

st = SegmentTree(num)
for i in range(n):
    x = A[i]
    l = max(x - k, 0)
    r = min(x + k + 1, num)
    now = st.query(l, r) + 1
    st.update(x, now)
print(max(st.dp))

Submission status: Time Limit Exceeded

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


seg = [0] * (1<<22)
def set_value(pos, val):
    pos += 1 << 21
    seg[pos] = val
    while (pos := pos//2) > 0:
        seg[pos] = max(seg[pos*2], seg[pos*2+1])

def get_max(ql, qr, sl=0, sr=1<<21, pos=1):
    if qr<=sl or sr<=ql:
        return 0
    if ql<=sl and sr<=qr:
        return seg[pos]
    sm = (sl+sr) // 2
    lmax = get_max(ql, qr, sl, sm, pos*2)
    rmax = get_max(ql, qr, sm, sr, pos*2+1)
    return max(lmax, rmax)

dp = [0] * (n+1)
for i in range(1, n+1):
    a = int(input())
    l = max(0, a-k)
    r = a + k + 1
    m = get_max(l, r)
    dp[i] = m + 1
    set_value(a, dp[i])

print(dp[n])

Submission status: Time Limit Exceeded

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


seg = [0] * (1<<23)
def set_value(pos, val):
    pos += 1 << 22
    seg[pos] = val
    while (pos := pos//2) > 0:
        seg[pos] = max(seg[pos*2], seg[pos*2+1])
     

def get_max(ql, qr, sl=0, sr=1<<22, pos=1):
    if qr<=sl or sr<=ql:
        return 0
    if ql<=sl and sr<=qr:
        return seg[pos]
    sm = (sl+sr) // 2
    lmax = get_max(ql, qr, sl, sm, pos*2)
    rmax = get_max(ql, qr, sm, sr, pos*2+1)
    return max(lmax, rmax)

dp = [0] * (400000)
for i in range(1, n+1):
    a = int(input())
    l = a - k
    r = a + k + 1
    m = get_max(l, r)
    dp[i] = m + 1
    set_value(a, dp[i])

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k = map(int,input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    DP = [[] for _ in range(n)]
    DP[1].append(0)
    M = 1
    for i in range(1,n):
        m = M
        flg = 0
        while m>0:
            for p in DP[m]:
                if abs(a[i]-a[p])<=k:
                    DP[m+1].append(i)
                    flg = 1
                    if m+1>M:
                        M=m+1
                    break
            if flg==1:
                break
            m -= 1
        if flg==0:
            DP[1].append(i)
    print(M)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
def dfs(idx, lastB, length):
    global ans
    if idx == N:
        ans = max(ans, length)
        return 

    dfs(idx+1, lastB, length)
    if abs(lastB-A[idx]) <= K:
        dfs(idx+1, A[idx], length+1)

dfs(0, A[0], 1)
dfs(0, A[1], 0)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[]
for i in range(n):
  x=int(input())
  l.append(x)
w=[]
for i in range(0,n):
  for j in range(i+1,n):
    if l[i]-l[j]>=k:
      if l[i] not in w:
        w.append(l[i])
      if l[j] not in w:
        w.append(l[j])
print(len(w))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
INF = 0

class MaxSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [-INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = max(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] >= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = -INF
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
mxA = max(A)
tree = MaxSegTree(mxA + 10)

for a in A:
    nx = tree.query(max(0, a - K), min(mxA + 1, a + K + 1))
    tree.update(a, nx + 1)

print(tree.query(0, mxA + 1))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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


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


def main():
    N, K = map(int, readline().split())
    A = list(int(readline()) for _ in range(N))
    Amax = max(A)
    dp = [0] * (Amax + 1)

    ide_ele = -float('inf')
    segtree = SegTree(dp, segfunc, ide_ele)

    for a in A:
        l = max(0, a - K)
        r = min(Amax, a + K)
        L = segtree.query(l, r + 1)
        segtree.update(a, L + 1)

    ans = segtree.query(0, Amax + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

list_a = []
max_a = 0
for _ in range(n):
    a = int(input())
    list_a.append(a)
    max_a = max(max_a, a)

# 意味合い的にはNoneの方がより正しいが、0で問題ない
dp = [0] * max_a

for a in list_a:
    i_latest_number = a - 1
    updated_length = 0
    for i in range(max(0, i_latest_number-k), min(max_a, i_latest_number+k+1)):
        updated_length = max(updated_length, dp[i]+1)
    dp[i_latest_number] = updated_length
#     print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

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

Amax = max(A)
# 初期化
n = 1
while n < Amax:
    n *= 2
#print(n)
# セグメント木を持つグローバル配列
# すべての値をINT_MAXに 
INF = 0
dat = [INF] * (2*n-1)

#k番目の値(0-indexed)をaに変更
def update(k,a):
    # 葉の節点
    k += n - 1
    dat[k] = a
    # 登りながら更新
    while k > 0:
        k = int((k - 1) / 2)
        dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2])

# [a,b]の最小値を求める
# 後ろのほうの引数は、計算の簡単のための引数。
# kは節点の番号、1, rはその節点が[1, r)に対応づいていることを表す。
# したがって、外からはquery(a, b, 0, 0, n)として呼ぶ。
def query(a,b,k,l,r):
    # [a,b]と[1, r)が交差しなければ、INT_MAX
    if a==b:
        return dat[n+a-1]
    
    if r <= a or b <= l:
        return INF
    # [a, b]が[1, r]を完全に含んでいれば、この節点の値 
    if a <= l and r <= b:
        return dat[k]
    # そうでなければ、2つの子の最小値
    else:
        vl = query(a,b,k * 2 + 1,l, int((l + r) / 2))
        vr = query(a,b, k * 2 + 2, int((l + r) / 2), r)
    
    return max(vl,vr)

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax,0,0,n)+1)
        #print(dat)
    print(dat[0])
main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


N, K, *A = map(int, open(0).read().split())
st = SegmentTree(300000 + 1, max, 0)

for a in A:
    st.update(a, st.query(max(a - K, 0), min(a + K + 1, 300000 + 1)) + 1)

print(st.query(0, 300000 + 1))

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



dp=[0]*(3*10**5+1)
seg=SegmentTree(dp, max, 0)
length=len(dp)
for i in range(N):
    a=int(input())
    if i==0:
        seg.update(a,1)
    else:
        left=max(0, a-K)
        right=min(length, a+K+1)
        now=seg.query(left, right)
        seg.update(a, now+1)

print(seg.query(0,length))