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:
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

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

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
memo:
GCD... INFをide_eleに設定して、片方がINFの場合はもう片方を返す
def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else return gcd(a,b)


vl = [1,4,6,8,9]

def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''

def main():
    n,k = map(int, input().split())
    seg = SegTree([0]*300001, max, 0)
    for _ in range(n):
        a = int(input())
        l = max(a-k,0)
        r = min(a+k,300000)
        c_max = seg.query(l,r+1)
        seg.update(a,c_max+1)

    ans = seg.query(0,300001)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

class SegTree():
    """
    0-indexedの配列[a0, a1, a2, ..., a(N-1)]に対して以下のクエリをそれぞれO(logx)で行う：
        1. i番目の要素にxを代入
        2. 半開区間[i, j)内の最小値を返す
    self.id_elemとself.funcを変えることでRmQ以外にも例えばRMQに対応可能。
    参考：https://juppy.hatenablog.com/entry/2019/05/02/蟻本_python_セグメント木_競技プログラミング_Atcoder
    """
    def __init__(self, N):
        #####identity element######
        self.id_elem = 0
        self.func = max

        #num_max: the smallest power of two over N
        self.num_max = 2 ** ((N - 1).bit_length())
        self.x = [self.id_elem] * (2 * self.num_max - 1)

    def get_elem(self, i):
        """
        i番目の要素を返す
        """
        return self.x[self.num_max + i - 1]

    def update(self, i, x):
        """
        i番目の要素にxを代入
        """
        i += self.num_max - 1
        self.x[i] = x
        while (i > 0):
            i = (i - 1) // 2
            self.x[i] = self.func(self.x[i * 2 + 1], self.x[i * 2 + 2])

    def query(self, i=0, j=-1):
        """
        半開区間[i, j)内の最小値を返す
        query()で配列全体に対してクエリを実行する
        """
        if j == -1: j = self.num_max
        i += self.num_max - 1
        j += self.num_max - 1
        res = self.id_elem
        
        while i < j:
            if i % 2 == 0:
                res = self.func(res, self.x[i])
                i += 1
            if j % 2 == 0:
                res = self.func(res, self.x[j - 1])
            i = (i - 1) // 2
            j = (j - 1) // 2
        return res

def main():
    N, K = map(int, input().split())
    """
    愚直に解けそうに無いのでdpを考える：dp[i][j] = (0~i番目まで見た時に最後の数がjで終わる部分列の最大長)
    このdpはO(N^2)なのでそのままでは実行不可能だが、ひとまず遷移を考えてみると
        dp[i][j] = max(dp[i-1][j-K], dp[i-1][j-K+1], ..., dp[i-1][j+K]) + 1
    ここのmaxをセグ木で導出すれば計算量はO(NlogN)で間に合う。
    """
    dp = SegTree(300001)
    for _ in range(N):
        a = int(input())
        # 最後がaで終わるケースのみ更新が入る
        now = dp.query(max(0, a - K), min(300001, a + K + 1))
        dp.update(a, now + 1)
    print(dp.query())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq

# SegTreeの関数
def segfunc(x, y):
    return max(x, y)
#区間の最小値、最大値を求めたい、区間の和を求めたいなど。segfuncに関数を書き込んでください。


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = - float('inf')


# セグメント木
class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """

    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番目の値をxに更新
        :param k: index(0-index)
        :param 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したものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        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 = MI()
    A = [0] * (6 * 10 ** 5 + 1)
    seg = SegTree(A, segfunc, ide_ele)
    for i in range(N):
        a = I()
        b = seg.query(max(0, a - K), a + K + 1)
        seg.update(a, b + 1)
    print(seg.query(1, 3 * 10 ** 5 + 1))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

class SegTree():
    def __init__(self, n_val, init_ele, combiner):
        self.n_val = n_val
        self.n = 1 << (self.n_val - 1).bit_length()
        self.tree = [init_ele] * (2 * self.n)
        self.combiner = combiner
        self.init_ele = init_ele

    def init_tree(self, data):
        self.data = data
        for x in range(self.n):
            self.tree[x + n] = self.data[x]
        for x in range(self.n - 1, 0, -1):
            self.tree[x] = self.combiner(self.tree[x<<1], self.tree[(x<<1) + 1])

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

    def update_single(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            self.tree[idx>>1] = self.combiner(self.tree[idx], self.tree[idx ^ 1])
            idx >>= 1


def solve():
    
    n, k = map(int, input().split())

    n_val = 3 * (10 ** 5)

    arr = [int(input()) for _ in range(n)]
    s_tree = SegTree(n_val, 0, max)

    for a in arr:
        s_tree.update_single(a, s_tree.query(max(a - k, 0), min(a + k, n_val) + 1) + 1)
    cout<<s_tree.query(1, n_val + 1)<<endl






def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300000)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300000))

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, segment_func, identity_element):
        self.n = n
        self.num = 1 << (self.n - 1).bit_length()
        self.segment_func = segment_func
        self.identity_element = identity_element
        self.segment_tree = [self.identity_element] * (2 * self.num)

    def initialize(self, val_arr):
        for i in range(self.n):
            self.segment_tree[self.num + i] = val_arr[i]
        for i in range(self.num - 1, 0, -1):
            self.segment_tree[i] = self.segment_func(self.segment_tree[2 * i], self.segment_tree[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.segment_tree[idx] = val
        while idx > 1:
            self.segment_tree[idx >> 1] = self.segment_func(self.segment_tree[idx], self.segment_tree[idx ^ 1])
            idx >>= 1

    def query(self, left, right):
        res = self.identity_element
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segment_func(res, self.segment_tree[left])
                left += 1
            if right & 1:
                res = self.segment_func(res, self.segment_tree[right - 1])
            left >>= 1
            right >>= 1
        return res

    def bisect_left(self, left, right, target):
        left += self.num
        right += self.num
        left_min = -1
        right_min = -1
        while left < right:
            if left & 1:
                if self.segment_tree[left] >= target and left_min == -1:
                    left_min = left
                left += 1
            if right & 1:
                if self.segment_tree[right - 1] >= target:
                    right_min = right - 1
            left >>= 1
            right >>= 1
        if left_min != -1 or right_min != -1:
            res = left_min if left_min != -1 else right_min
            while res < self.num:
                if self.segment_tree[2 * res] >= target:
                    res *= 2
                else:
                    res *= 2
                    res += 1
            return res - self.num
        else:
            return self.n


def main():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    max_val = 3 * 10 ** 5
    st = SegmentTree(max_val + 1, max, 0)
    for aa in a:
        st.update(aa, st.query(max(0, aa - k), min(max_val, aa + k) + 1) + 1)
    print(st.query(1, max_val + 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class SegTree:
    def __init__(self, N, ele):
        self.num = 2**(N-1).bit_length()
        self.el = ele
        self.data = [ele]*(2*self.num)

    def calc(self, x, y):
        return max(x, y)

    def update(self, idx, x):
        idx += (self.num - 1)
        self.data[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])

    def query(self, l, r):
        L = l + self.num
        R = r + self.num
        res = self.el
        while L < R:
            if L & 1:
                res  = self.calc(res, self.data[L-1])
                L += 1
            if R & 1:
                R -= 1
                res = self.calc(res, self.data[R-1])
            L >>= 1
            R >>= 1
        return res
    
    def get(self, idx):
        idx += (self.num - 1)
        return self.data[idx]

n, k = map(int, input().split())
A = [int(input()) for _ in range(n)]
seg = SegTree(330000, 0)
max_a = 300010
for a in A:
    l = max(0, a-k)
    r = min(max_a, a+k+1)
    now = seg.query(l, r)
    seg.update(a, now+1)

print(seg.query(0, max_a))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

class SegTree:
    def __init__(self, N, ele):
        self.num = 2**(N-1).bit_length()
        self.el = ele
        self.data = [ele]*(2*self.num)

    def calc(self, x, y):
        return max(x, y)

    def update(self, idx, x):
        idx += (self.num - 1)
        self.data[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])

    def query(self, l, r):
        L = l + self.num
        R = r + self.num
        res = self.el
        while L < R:
            if L & 1:
                res  = self.calc(res, self.data[L-1])
                L += 1
            if R & 1:
                R -= 1
                res = self.calc(res, self.data[R-1])
            L >>= 1
            R >>= 1
        return res
    
    def get(self, idx):
        idx += (self.num - 1)
        return self.data[idx]

n, k = map(int, input().split())
A = [int(input()) for _ in range(n)]
seg = SegTree(330000, 0)
max_a = 300010
for a in A:
    l = max(0, a-k)
    r = min(max_a, a+k+1)
    now = seg.query(l, r)
    seg.update(a, now+1)

print(seg.query(0, max_a))

Submission status: Accepted

Solution code:
import typing

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

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 = _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 __setitem__(self, p: int, x: typing.Any) -> None:
        self.set(p, x)

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

        return self._d[p + self._size]
    
    def __getitem__(self, p: int, x: typing.Any) -> None:
        return self.get(p, x)

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

n, k, *A = map(int, open(0).read().split())
m = 300009
segtree = SegTree(op=max, e=0, v=m)
for a in A:
    l, r = max(0, a-k), min(m, a+k+1)
    segtree[a] = segtree.prod(l, r)+1
print(segtree.all_prod())

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        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
        # k+1ではなくkでは？
        while k+1:
            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

import sys;input=sys.stdin.readline
N, K = map(int, input().split())
X = []
for _ in range(N):
    a, = map(int, input().split())
    X.append(a)
mX = max(X)
ss = SegTree([0] * (mX+1), mX+1, -1, max)
for i in range(N):
    x = X[i]
    t = ss.query(max(x-K, 0), min(x+K+1, mX+1))
#    print(x, 1+t, max(x-K, 0), min(x+K+1, mX))
    ss.update(x, 1+t)
print(ss.query(0, mX+1))

Submission status: Accepted

Solution code:
import typing

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

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 = _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
    
    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

n, k, *A = map(int, open(0).read().split())
m = 300009
segtree = SegTree(op=max, e=0, v=m)
for a in A:
    l, r = max(0, a-k), min(m, a+k+1)
    segtree.set(a, segtree.prod(l, r)+1)
print(segtree.all_prod())

Submission status: Accepted

Solution code:
def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, size):
        self.size = 2**((size-1).bit_length())
        self.e = -1
        self.val = [self.e]*(self.size*2)
    
    def op(self, a, b):
        return max(a, b)
    
    def update(self, i, x):
        i += self.size
        self.val[i] = x
        
        while i > 0:
            i = i >> 1
            self.val[i] = self.op(self.val[2*i], self.val[2*i+1])
    
    def query(self, l, r):
        l += self.size
        r += self.size

        l_sum = 0
        r_sum = 0

        while l < r:
            if l & 1:
                l_sum = self.op(l_sum, self.val[l])
                l += 1
            l = l >> 1

            if r & 1:
                r -= 1
                r_sum = self.op(r_sum, self.val[r])
            r = r >> 1

        return self.op(l_sum, r_sum)

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

max_val = 300000

dp = SegmentTree(max_val + 1)

for i in range(N):
    dp.update(A[i], dp.query(max(0, A[i] - K), min(max_val, A[i] + K) + 1) + 1)
print(dp.query(1, max_val + 1))

Submission status: Accepted

Solution code:


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

A = [int(input()) for _ in range(N)]

st = SegmentTree(300000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, 300001)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)