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: Accepted

Solution code:
class SegmentTree:
    '''
    Segment tree。区間を表す関数の引数は全て閉区間で統一する(search系の戻り値を考慮)
    --------
    n:要素数, func:演算(モノイド), e:単位元(モノイド), init_list:初期値
    '''
    def __init__(self, n, func=lambda x, y : max(x, y), e = -float('inf'), init_list = None):
        assert n > 0 and (not init_list or len(init_list) <= n)
        self.n = n
        self.leaf_n = 1
        while n > self.leaf_n:
            self.leaf_n <<= 1
        self.node_n = (self.leaf_n << 1) - 1
        self.offset = self.leaf_n - 1
        self.tree = [e] * self.node_n
        self.f = func
        self.e = e

        if init_list:
            self.tree[self.offset:self.offset+n] = init_list
            self.update_all()
    
    def set_values(self, val_list):
        n = len(val_list)
        assert self.leaf_n >= n
        self.tree[self.offset:self.offset+n] = val_list
    
    def set_value(self, index, val):
        assert 0 <= index < self.leaf_n
        self.tree[self.offset+index] = val

    def get_value(self, index):
        assert 0 <= index < self.leaf_n
        return self.tree[self.offset + index]

    def update_all(self):
        l = self.offset
        n = self.leaf_n
        while l > 0:
            for i in range(l, l + n, 2):
                self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            l >>= 1
            n >>= 1

    def update(self, index, val):
        assert 0 <= index < self.leaf_n
        i = self.offset + index
        self.tree[i] = val
        while i > 0:
            if i & 1 == 0:
                i -= 1
            self.tree[i>>1] = self.f(self.tree[i], self.tree[i+1])
            i >>= 1

    def query(self, l, r):
        '''
        閉区間[l, r]の演算結果
        '''
        assert 0 <= l <= r < self.leaf_n
        left_val = self.e
        right_val = self.e
        l += self.offset
        r += self.offset
        while l < r:
            if l & 1 == 0:
                left_val = self.f(left_val, self.tree[l])
            if r & 1 == 1:
                right_val = self.f(self.tree[r], right_val)
                r -= 1
            l >>= 1
            r = (r >> 1) - 1
        if l == r:
            left_val = self.f(left_val, self.tree[l])
        return self.f(left_val, right_val)

    def search_max_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の r を返す。存在しない場合-1を返す。check_func(e)はTrueである必要がある。
        --------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x):x <= v
        '''
        assert(0 <= l < self.leaf_n and check_func(self.e))
        i = l + self.offset
        if not check_func(self.tree[i]):
            return -1
        left_val = self.e
        while True:
            while i & 1 != 0: # iを左端とする最上の層まで移動
                i >>= 1
            x = self.f(left_val, self.tree[i])
            if not check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側に移動
                    x = self.f(left_val, self.tree[i])
                    if check_func(x):
                        left_val = x
                        i += 1
                return i - self.offset - 1
            left_val = x
            i += 1
            if i & (i + 1) == 0:
                return self.n - 1
    
    def search_min_right(self, l, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の r を返す。存在しない場合-1を返す。
        --------
        例：最大値がv以上になる区間を探す
            f = max
            check_func = lambda(x):x >= v
        '''
        assert(0 <= l < self.leaf_n)
        i = l + self.offset
        left_val = self.e
        while True:
            x = self.f(left_val, self.tree[i])
            if check_func(x):
                while i < self.offset:
                    i = (i << 1) + 1 #下の左側
                    x = self.f(left_val, self.tree[i])
                    if not check_func(x):
                        left_val = x
                        i += 1
                j = i - self.offset
                if self.n <= j:
                    return -1
                return j if check_func(self.f(left_val, self.tree[i])) else -1
            if i & 1 == 0:
                left_val = x
            if (i + 1) & (i + 2) == 0: #iが右端
                return -1
            i >>= 1


    def search_min_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最小の l を返す。check_func(e)はTrueである必要がある。
        --------
        例：最大値がv以下になる区間を探す
            f = max
            check_func = lambda(x): x <= v
        '''
        assert(0 <= r < self.leaf_n and check_func(self.e))
        i = r + self.offset
        if not check_func(self.tree[i]):
            return -1
        right_val = self.e
        while True:
            while i & 1 == 0 and i > 0: # iを右端とする最上の層まで移動
                i = (i - 1) >> 1
            x = self.f(self.tree[i], right_val)
            if not check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 #iを右端とする1個下の層に移動
                    x = self.f(self.tree[i], right_val)
                    if check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset + 1
            right_val = x
            if i & (i + 1) == 0:
                return 0
            i -= 1

    def search_max_left(self, r, check_func):
        '''
        閉区間 [l, r] の演算結果 x が check_func(x) == True となるような最大の l を返す。存在しない場合-1を返す。
        --------
        例：最大値がv以上になる区間を探す
            f = max
            check_func = lambda(x):x >= v
        '''
        assert(0 <= r < self.leaf_n)
        i = r + self.offset
        right_val = self.e
        while True:
            x = self.f(self.tree[i], right_val)
            if check_func(x):
                while i < self.offset:
                    i = (i + 1) << 1 #下の右側
                    x = self.f(self.tree[i], right_val)
                    if not check_func(x):
                        right_val = x
                        i -= 1
                return i - self.offset if check_func(self.f(self.tree[i], right_val)) else -1
            if i & 1 == 1:
                right_val = x
            if i & (i + 1) == 0: #iが左端
                return -1
            i = (i >> 1) - 1

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

dp = SegmentTree(max_val+1, max, 0)
i = 0
for _ in range(n):
    a = int(input())
    left = max(0, a-k)
    right = min(max_val, a+k)
    x = dp.query(left, right)
    dp.update(a, x+1)
print(dp.query(0, max_val))

Submission status: Accepted

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+1,300001)
  v = ST.prod(l,r)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)

Submission status: Accepted

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

class SegTree():
    def __init__(self, size, segfunc, ide_ele):
        self.size = 2**(size-1).bit_length()
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.tree = [ide_ele]*(self.size*2)
    def update(self, k, a):
        k += self.size
        self.tree[k] = a
        while k > 0:
            k >>= 1
            self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.ide_ele, self.ide_ele
        while l<r:
            if(l&1):
                lres = self.segfunc(lres,self.tree[l])
                l+=1
            if(r&1):
                r-=1
                rres = self.segfunc(self.tree[r],rres)
            l >>= 1
            r >>= 1
        res = self.segfunc(lres,rres)
        return res

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

seg = SegTree(700000, max, 0)
memo = [0] * 700000

for i in range(n):
    a = int(input())
    v = seg.query(max(a-k,0), a+k+1)
    if memo[a] < v + 1:
        memo[a] = v + 1
        seg.update(a, v + 1)
    
print(max(memo))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# 処理する区間の長さはmax_A
N0 = 2**(max_A).bit_length()
init_val = 0
data = [init_val]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k > 0:
        k = (k - 1) / 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = init_val
    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 i,a in enumerate(A):
    update(a,query(max(a-K,0),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Accepted

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

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

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

#####単位元######
ide_ele = -1

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

A = [0]*(300005)
init(A)

for _ in range(N):
    a = int(input())
    nax = query(max(0,a-K),min(300001,a+K+1))
    if nax >= A[a]:
        update(a,nax+1)
    
print(query(0,300001))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
from fractions  import gcd


n,k=map(int,input().split())
inf = 0
m=300001
num_min =2**(m-1).bit_length()
dat=[inf]*(2*num_min-1)

#初期化

#親のノード(n-1)//2
#子のノード2n+1,2n+2

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

def update(i,x):
    i+=num_min-1
    dat[i]=x
    while i>0:
        i=(i-1)//2
        dat[i]=segfunc(dat[2*i+1],dat[2*i+2])
def query(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res = segfunc(res,dat[a])
        if b&1==1:
            res = segfunc(res,dat[b])
            b-=1
        a=a//2
        b=(b-1)//2
    if a==b:
        res = segfunc(res,dat[a])
    else:
        res=segfunc(segfunc(res,dat[a]),dat[b])
    return res

ans=0
for i in range(n):
    x=int(input())
    l=max(0,x-k)
    r=min(300000,x+k)
    tmp=query(l,r+1)+1
    ans=max(tmp,ans)
    update(x,tmp)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# 処理する区間の長さはmax_A
N0 = 2**(max_A).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k > 0:
        k = (k - 1) / 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    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 i,a in enumerate(A):
    update(a,query(max(a-K,0),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# 処理する区間の長さmax_A
N0 = 2**(max_A).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k > 0:
        k = (k - 1) / 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    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 i,a in enumerate(A):
    update(a,query(max(a-K,0),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
max_A=max(A)

# max_Aが処理する区間の長さ
N0 = 2**(3*10**5-1).bit_length()
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最大値
def query(l, r):
    L = l + N0; R = r + N0
    s = float("-inf")
    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 i,a in enumerate(A):
    update(a,query(max(a-K,0),min(a+K+1,max_A+1))+1)

print query(0,max_A+1)

Submission status: Accepted

Solution code:
def op(a:int, b:int): return max(a, b)#セグ木で使う関数
class Segtree():#親のノードを１とするスタート
    def __init__(self, n, segfunc=max, init=0):
        self.n  = n
        self.segfunc = segfunc
        self.init = init
        self.num = 1 << (self.n-1).bit_length() #最下層の数:2**n個
        self.tree = [self.init]*2*self.num #最も頂点の親ノードが1スタートなのでn個必要


    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:#^排他的論理和
            #tree[1]まで操作する
            self.tree[k>>1] = self.segfunc(self.tree[k], self.tree[k^1])
            k>>=1

    def query(self, l, r):#[l, r)の区間であることに注意
        if r<=l: return self.init
        l += self.num
        r += self.num
        res = self.init
        while(r>l):#rがlより大きい間
            if l&1:#ノードが右側なら評価
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r&1:#ノードが右側なら左側の値を入れる。
                r -= 1
                res = self.segfunc(res, self.tree[r])
            l = l//2
            r = r//2
        return res

n, k = map(int, input().split())
max_a = 3*10**5+7
st = Segtree(max_a)
for i in range(n):
    a = int(input())
    temp = st.query(max(0, a-k), min(a+k+1, max_a+1))+1
    st.update(a, temp)

print(st.tree[1])

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y): #演算の選択（今回は最大値）
    return max(x, y)
#################

#####ide_ele#####
ide_ele = -1      #単位元（任意のものとsegfuncした時、その値をかえないようなもの。）
#################

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番目の値を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, 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

      
#ここから本処理

#やりたいこと: data[i][n] = (左からi番目までを見た時に、最後がnで終わる部分列の最大の長さ)
# 更新: data[i+1][A[i+1]] = max{data[i][n] | n s.t. abs(A[i+1]-n) <= K} +1
#       ※ A[i+1]以外のnについては、data[i+1][n] = data[i][n]

# 高速化が必要
# 考察： 1, iを1ずつ増やすループで、data[i]から値が変更するのは data[i+1][A[i+1]]だけ。
#            →data[i][n]を二次元配列で持つのは無駄が多い。
#             単にdata[n]として、A[i+1]のところだけ更新すれば十分。
#       2, data[A[i+1]]の更新のとき、abs(A[i+1]-n) <= K を満たすnから、
#          data[n]の最大値を選ぶ必要あり。
#            →愚直に調べるとK回かかってしまう。
#             区間[A[i+1]-K, A[i+1]+K]の最大値を素早く知るため、セグメントツリーを使う。

# セグメントツリーでできること：
#      1, 配列の一つの要素を更新する。(O(logN))
#      2, 任意の区間[a,b]の中で、配列data[a:b]の最大値を求める。
#         ※なお、「最大」だけでなく「最小」や「和」、「行列の積」などについても適用可能(結合律と単位元)。

N, K = map(int,input().split())
Num_max = 3*10**5 + 1

A = [int(input()) for _ in range(N)]
# 配列 data = [0,0,0,…](初期値は0番目まで見た時の最長部分列の長さなので全て0) をセグメントツリー化する。
# 初期値、使いたい演算（最大）、その演算の単位元を入力
st = SegTree([0 for _ in range(Num_max+4)], segfunc, ide_ele) #「+4」に意味はないです。十分大きければ良いです。

st.update(A[0], 0)  
for i in range(N):
  l = st.query(max(A[i] - K, 0), min(A[i] + K+1, Num_max)) # 半開区間[A[i]-K, A[i]+K+1)の最大値を取得
  st.update(A[i], l+1)  # data[A[i]]をl+1で更新(73行目の漸化式)。

print(st.query(0, Num_max)) #配列中で最大の要素を取得。

Submission status: Accepted

Solution code:
def segfunc(x,y):#自分で設定
    return max(x,y)

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

ide_ele = -1 #単位元 自分で設定してね

N , K = map(int,input().split())
n = 300001
num =2**(300000).bit_length() #num:n以上の最小の2のべき乗
seg=[ide_ele]*2*num
a = [int(input()) for i in range(N)]
dp = [0 for i in range(300001)]
init(dp)

for i in range(N):
    now = query(max(0,a[i]-K),min(300001,a[i]+K+1))+1
    update(a[i],now)

print(query(0,300001))

Submission status: Accepted

Solution code:

## https://atcoder.jp/contests/abc170/submissions/14416787
class SegmentTree():
    def __init__(self,n,init):
        self.offset=2**((n-1).bit_length())
        self.tree=[init]*(2*self.offset)
        self.init=init
    def update(self,pos,val):
        pos+=self.offset
        self.tree[pos]=val
        while pos>1:
            pos=pos//2
            self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
    def query(self,l,r):
        l+=self.offset
        r+=self.offset
        ret=self.init
        while l<=r:
            ret=max(ret,self.tree[r])
            r=(r-1)//2
            ret=max(ret,self.tree[l])
            l=(l+1)//2
        return ret

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]

st=SegmentTree(300001,0)
##queryが開区間でない
for ai in a:
    l=max(0,ai-k)
    r=min(300001,ai+k)
    m=st.query(l,r)
    st.update(ai,m+1)

print(st.query(0,300001))

Submission status: Accepted

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)

M = max(T)+1
A = [0]*M
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, M))
    s_tree.update(a, p + 1)

print(s_tree.query(0, M))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
最後のお値にしか依存しない
"""
def main():
    mod=10**9+7
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)

        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])

        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            t = self.ide_ele
            while L < R:
                if L & 1:
                    s = self.segf(s,self.data[L])
                    L += 1
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        # セグ木上で二分探索，[l,r)の範囲でcheck関数を満たす最小の値をとるところのindexを返す．
        # reverse=Trueなら最大値かな
        # ない時の返り値がNoneなことに注意
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1

            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0
            
    N,K=MI()
    M=3*10**5
    seg=Segtree([0]*(M+5), 0, segf=max)
    
    for i in range(N):
        a=I()
        l=max(a-K,0)
        r=min(M,a+K)
        temp=seg.query(l,r+1)
        seg.update(a,temp+1)
        
    ans=seg.query(0,M+1)
    print(ans)

main()

Submission status: Accepted

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: Accepted

Solution code:
class SegTree:
	"""
	1-indexed
	"""
	def __init__(self,size,funcComp,funcUpd,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = funcComp		# suppose to min or max
		self.updateFunc = funcUpd		# suppose to add or update
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		# num:size以上の最小の2のべき乗
		self.datSize = 2**size.bit_length()

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		"""
		i: index(1-indexed)
		bottom-up
		"""
		# i -= 1	# 1-orderで指定され、内部では0-Order想定?
		# i += (self.datSize - 1)
		i += self.datSize
		self.datTree[i] = self.updateFunc(self.datTree[i],val)
		while 0 < i:
			i >>= 1
			self.datTree[i] = self.compareFunc( self.datTree[i<<1|0], self.datTree[i<<1|1] )

	def query(self,a,b):
		""" get minimun/maximum value of range[a,b)
		non-recursive
		bottom-up
		all 1-indexed
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:

			if b & 1:
				# shrink right
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b])

			if a & 1:

				# shrink left
				ret = self.compareFunc(ret, self.datTree[a])
				a += 1

			a >>= 1; b >>= 1

		return ret

	def printLeaf(self):
		print(self.datTree[self.datSize-1:])

def update(x,val):
	return val


def LongestSeaquence(A,K):
	N = len(A)
	lis = 0

	# === Range Maximum Query ===
	MAX_A = max(A)
	tree = SegTree(MAX_A,max,update,0,-1e18)
	# tree.update( 0, 1 )

	for n in range(N):
		x = A[n]
		l = max(0,x-K)
		r = min(MAX_A,x+K)
		tmp = tree.query(l,r+1)+1
		tree.update( x, tmp )
		# lis = max(lis, tmp)

	lis=tree.query(0,MAX_A)

	return lis

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

	print(LongestSeaquence(A,K))



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        for i in range(self.n):
            self.tree[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x
        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        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 all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

#import
#import math
#import numpy as np
#= int(input())
#= input()
def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]

    MAX_A = 300005

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

    ans = dp.all_query()
    print(ans)

if __name__ == "__main__":
    main()