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:
import typing

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

class SegTree:
    '''
    op: 結合律が成り立つ演算
    e: 単位元 A op e = A and e op A = A が成り立つe
    足し算の場合 0, 掛け算の場合 1
    '''
    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 = _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:
        """
        d[p]にxを代入
        d[p]が変更された分を他の部分に反映する
        O(logn)
        """
        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:
        """
        d[p]を返す
        O(1)
        """
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        """
        op(d[left],・・・,d[right-1])を返す
        O(logn)
        """
        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:
        """
        op(d[0],・・・,d[n-1])を返す
        O(1)
        """
        return self._d[1]
    
    def max_right(self,
                left: int,
                f: typing.Callable[[typing.Any], bool]
                ) -> int:
        """
        fが単調とすれば、f(op(d[left],・・・,d[right-1])) = true
        となる最大のrightを求められる
        O(logn)
        """
        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:
        """
        fが単調とすれば、f(op(d[left],・・・,d[right-1])) = true
        となる最小のleftを求められる
        O(logn)
        """

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



def main():
    N: int
    K: int
    A: list
    MAX_A: int = 300005
    N, K = map(int, input().split())
    A = list(int(input()) for _ in range(N))
    seg = SegTree(max,0,MAX_A)
    for i in range(N):
        x: int = A[i]
        left = max(0, A[i] - K)
        right = min(MAX_A, A[i] + K + 1)
        now = seg.prod(left, right) + 1
        seg.set(x, max(now, seg.get(x)))

    print(seg.all_prod())

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#入力の高速化
import sys
input = sys.stdin.readline

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

#####ide_ele#####
ide_ele =-float('inf')
#################

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


v = [-float('inf')]*(pow(10,5)*3+1)
seg = SegTree(v, segfunc, ide_ele)

# dp[i]:最終要素が1の時に作れる最長部分列
for i in a:
    r=min(i+k+1,3*pow(10,5)+1)
    l=max(i-k,0)
    if seg.query(l, r)==-float('inf'):
        seg.update(i, 1)
    else:
        x=seg.query(l, r)
        seg.update(i,x+1)

print(seg.query(0,pow(10,5)*3+1))

Submission status: Accepted

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

class SegmentTree:
    def __init__(self,n,ele):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


    #####segfunc######
    #クエリに応じて変える
    def segfunc(self,x,y):
        return max(x,y)

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    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,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

st=SegmentTree(300001,0)
dp=[0]*n
for i in range(n):
    a=int(input())
    dp[i]=max(dp[i],st.query(max(0,a-k),min(300000,a+k)+1)+1)
    st.update(a,dp[i])
    dp[i]=max(dp[i],st.query(0,300001))
print(dp[n-1])

Submission status: Accepted

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, a + K) + 1)
    tree.update(a, nx + 1)

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
scale = 21
#scale = 4
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(rdb)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1))
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        for Z in range(X,Y):
          maxi = max(maxi,seg[db[i]+Z])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,rdb[i],maxi)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Submission status: Accepted

Solution code:
class Segment_Tree():
    """
    このプログラム内は1-index
    """

    def __init__(self,L,calc,unit):
        """calcを演算とするリストLのSegment Treeを作成

        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        N=len(L)
        d=max(1,(N-1).bit_length())
        k=1<<d

        self.data=[unit]*k+L+[unit]*(k-len(L))
        self.N=k
        self.depth=d

        for i in range(k-1,0,-1):
            self.data[i]=calc(self.data[i<<1],self.data[i<<1|1])

    def get(self,k,index=1):
        """第k要素を取得
        """
        assert 0<=k-index<self.N,"添字が範囲外"
        return self.data[k-index+self.N]

    def update(self,k,x,index=1):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """
        assert 0<=k-index<self.N,"添字が範囲外"
        m=(k-index)+self.N
        self.data[m]=x

        while m>1:
            m>>=1
            self.data[m]=self.calc(self.data[m<<1],self.data[m<<1|1])


    def product(self,From,To,index=1,left_closed=True,right_closed=True):
        L=(From-index)+self.N+(not left_closed)
        R=(To-index)+self.N+(right_closed)

        vL=self.unit
        vR=self.unit

        while L<R:
            if L&1:
                vL=self.calc(vL,self.data[L])
                L+=1

            if R&1:
                R-=1
                vR=self.calc(self.data[R],vR)

            L>>=1
            R>>=1

        return self.calc(vL,vR)

    def all_product(self):
        return self.data[1]
#================================================
N,K=map(int,input().split())
A=[0]*N
for i in range(N):
    A[i]=int(input())

T=max(A)
S=Segment_Tree([0]*(T+1),max,0)

for i in range(N-1,-1,-1):
    S.update(A[i],S.product(max(0,A[i]-K),min(T,A[i]+K),0)+1,0)

print(S.all_product())

Submission status: Accepted

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

#####ide_ele#####
ide_ele = float('-inf')
#################

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 = [0] * 300001
seg = SegTree(a, segfunc, ide_ele)
ans = 0
for _ in range(N):
    x = int(input())
    tmp = seg.query(max(0, x - K), min(300001, x + K + 1))
    ans = max(ans, tmp + 1)
    seg.update(x, tmp + 1)
print(ans)

Submission status: Accepted

Solution code:
class Segtree():
    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

a_max = max(a) + 1
seg_dp = Segtree(a_max)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, a_max))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
class Segtree():
    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

# 解説AC
a_max = max(a) + 1
seg_dp = Segtree(a_max)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, a_max))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
class Segtree():

    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

# 解説AC
a_max = max(a) + 1
seg_dp = Segtree(a_max)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, a_max))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
class Segtree():

    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

# 解説AC
segmax = max(a) + 1
seg_dp = Segtree(segmax)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, segmax))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def MI():
    return map(int, input().split())

class segtree:
    # 1-indexed セグ木
    x_unit=0 # 単位元
    x_func=max  # 関数
    condition=lambda self,a,b:a>=b # max_right用に定義
    def __init__(self,n,seq): # 元のseqと要素数n
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n): # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def get(self, i): # 値を入手
        return self.x[i+self.n] 
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)
    def max_right(self, l, v): 
        # index lを含めて右にある値の中でa[j]>=vを満たす最小のindexを求める
        # 存在しない場合はnを出力
        r=self.n
        if self.condition(self.fold(l, r),v)==False:
            return r
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return l
    def min_left(self, r, v): 
        # index rを含まずに左にある値の中でa[j]>=vを満たす最大のindexを求める
        # 存在しない場合は0を出力
        l=0
        if self.condition(self.fold(l, r),v)==False:
            return l
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return r

n,k=MI()
seq=[0 for _ in range(300001)]
seg=segtree(300001,seq)
for i in range(n):
    a=int(input())
    left=seg.fold(max(a-k,0), a+1)
    right=seg.fold(a, min(a+k,300000)+1)
    seg.update(a,max(left,right)+1)
print(seg.fold(0, 300001))

Submission status: Accepted

Solution code:
class Segtree():

    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

num = max(a) + k + 1
seg_dp = Segtree(num)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, num))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
class Segtree():

    def __init__(self, n):
        self.num = 1 << (n - 1).bit_length()
        self.tree = [0] * 2 * self.num
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = max(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] = max(self.tree[k], self.tree[k ^ 1])
            k >>= 1

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


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

num = max(a) + k + 1
seg_dp = Segtree(num)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, num))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

Solution code:
class Segtree():  # Segtree

    ide_ele = 0  # 初期値(単位元)

    def segfunc(self, x, y):  # 区間にしたい操作
        return max(x, y)  # ex) max,min,gcd,lcm,sum,product

    def __init__(self, n):  # LIST: 配列の初期値
        self.num = 1 << (n - 1).bit_length()
        self.tree = [Segtree.ide_ele] * 2 * self.num
        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 += 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())
a = [int(input()) for _ in range(n)]

num = max(a) + k + 1
seg_dp = Segtree(num)
for ai in a:
    tmp = seg_dp.query(max(ai - k, 0), min(ai + k + 1, num))
    seg_dp.update(ai, tmp + 1)
print(max(seg_dp.tree))

Submission status: Accepted

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

Amax = 3*10**5

# N: 処理する区間の長さ
N0 = 2**(Amax-1).bit_length()
INF = 0
data = [INF]*(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 = 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

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)+1)
        #print(data)
    print(data[0])
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def solve(inp):
    def bit_length(x):
        ret = 0
        while x:
            x >>= 1
            ret += 1
        return ret

    n = 300001
    ide_ele = 0
    num = 1 << bit_length(n)
    seg = [ide_ele] * 2 * num

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

    def init(init_arr):
        for i in range(n):
            seg[i + num - 1] = init_arr[i]
        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 = inp[0]
    d = inp[1]
    A = inp[2:]
    arr = np.zeros(n, dtype=np.int64)
    init(arr)

    for a in A:
        l = max(0, a - d)
        r = min(a + d + 1, n)
        v = query(l, r)
        update(a, v + 1)
    return query(0, n)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

from my_module import solve

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)