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 sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    A = list(int(input()) for _ in range(n))
    MAX = max(A) + 1
    seg = SegTree([0 for _ in range(MAX)], lambda x, y: max(x, y), -f_inf)
    res = [0] * MAX
    for a in A:
        left = max(0, a - k)
        right = min(MAX + 1, a + k + 1)
        ma = seg.query(left, right)
        seg.update(a, ma + 1)
        res[a - 1] = ma + 1

    print(max(res))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:

from collections import defaultdict
from bisect import bisect

n, k = list(map(int, input().split()))
al = [0] * n
for i in range(n):
    al[i] = int(input())
max_al = max(al)
min_al = min(al)

# N: 処理する区間の長さ
N = max(al)+1
N0 = 2**(N-1).bit_length()
INF = 2**31-1
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] = min(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 = min(s, data[R-1])

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


for i in range(n):
    update(al[i], n)

for a in al:
    v = query(max(min_al, a-k), min(a+k, max_al)+1)
    update(a, n-((n-v)+1))
v = query(min_al, max_al+1)
print(n-v)

Submission status: Accepted

Solution code:
class SegmentTreeMAX():
    def __init__(self,A,n,ide_ele_max=-1):
        self.ide_ele_max = ide_ele_max
        self.num_max =2**(n-1).bit_length()
        self.seg_max=[ide_ele_max]*2*self.num_max
        #set_val
        for i in range(n):
            self.seg_max[i+self.num_max-1]=A[i]
        #built
        for i in range(self.num_max-2,-1,-1) :
            self.seg_max[i]=max(self.seg_max[2*i+1],self.seg_max[2*i+2])

    def update_max(self,k,x):
        k += self.num_max-1
        self.seg_max[k] = x
        while k:
            k = (k-1)//2
            self.seg_max[k] = max(self.seg_max[k*2+1],self.seg_max[k*2+2])

    def query_max(self,p,q):
        if q<=p:
            return self.ide_ele_max
        p += self.num_max-1
        q += self.num_max-2
        res=self.ide_ele_max
        while q-p>1:
            if p&1 == 0:
                res = max(res,self.seg_max[p])
            if q&1 == 1:
                res = max(res,self.seg_max[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = max(res,self.seg_max[p])
        else:
            res = max(max(res,self.seg_max[p]),self.seg_max[q])
        return res

N,K=list(map(int,input().split()))
T = [0]*(300001)
SegTree = SegmentTreeMAX(T,300001)
for i in range(N):
    A=int(input())
    X=SegTree.query_max(max(0,A-K),min(A+K,300000)+1)
    SegTree.update_max(A,X+1)
    T[A]=X+1
print(SegTree.query_max(0,300000+1))

Submission status: Accepted

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

MOD = 10 ** 9 + 7
INF = 2 * 10**18

in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]


# 1点更新・区間クエリ（0-index）
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 get(self, k):
        k += self.num
        return self.tree[k]


def main():

    M = 3 * 10**5 + 10
    N, K = in_nn()
    A = [0] * N

    for i in range(N):
        A[i] = in_n()

    seg = SegTree([0] * M, segfunc=lambda a, b: max(a, b), ide_ele=0)

    for i in range(N):
        now = A[i]
        left = max(0, now - K)
        right = min(now + K + 1, M)
        u = seg.query(left, right)
        seg.update(now, u + 1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

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

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
Ma=max(A)
Tree=[0]*(Ma+1)
seg = SegTree(Tree, segfunc, ide_ele)
ans=0
for i in range(N):
    a=A[i]
    l=max(0,a-K)
    r=min(a+K,Ma)
    Ans=seg.query(l,r+1)
    seg.update(a, Ans+1)
    ans=max(ans,Ans+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,k=map(int,input().split())
n=300_003
def update(i,x):#A[i]=x
	now=2**deep+i
	seg[now-1]=x
	while now>1:
		now//=2
		seg[now-1]=min(seg[now*2-1],seg[now*2])
def minimum(x,y):#A[x]からA[y]の最小値	
	s=inf
	l=x+2**deep
	r=y+2**deep+1
	while l<r:
		if l%2==1:
			s=min(s,seg[l-1])
			l+=1
		if r%2==1:
			r-=1
			s=min(s,seg[r-1])
		l//=2
		r//=2
	return s
inf=0
deep=(n-1).bit_length()
seg=[inf]*(2**deep*2-1)
for i in range(N):
	a=int(input())
	x=max(a-k,0)
	y=min(a+k,n)
	update(a,minimum(x,y)-1)
print(-minimum(0,n-1))

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
L = [int(input()) for _ in range(N)]
A = [[] for _ in range(N)]
tmp = 0
A[0].append(L[0])
for num in L[1:]:
  for i in reversed(range(0,tmp+1)):
    for a in A[i]:
      if abs(a-num) <= K:
        A[i+1].append(num)
        tmp = max(tmp,i+1)
        break
    else:
      continue
    break
  else:
    A[0].append(num)
print(tmp+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
#####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 += 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
Ma=max(A)
Tree=[0]*(Ma+1)
seg = SegTree(Tree, segfunc, ide_ele)
ans=0
for i in range(N):
    a=A[i]
    l=max(0,a-K)
    r=min(a+K,Ma)
    Ans=seg.query(l,r+1)
    seg.update(a, Ans+1)
    ans=max(ans,Ans+1)
print(ans)

Submission status: Accepted

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

import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# from atcoder.fenwicktree import FenwickTree

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


import typing


# from atcoder.segtree import SegTree

LARGE = 3*10**5

def solve(arr, k):  # fix inputs here
    console("----- solving ------")
    console(arr,k)

    segtree = SegTree(max, -1, LARGE+2)

    maxres = 0

    for a in arr:
        maxval = 0

        maxsmall = max(0, a - k)
        minlarge = min(LARGE, a + k) + 1
        maxval = max(maxval, segtree.prod(maxsmall, minlarge))

        maxval += 1
        maxres = max(maxres, maxval)

        console(a, maxsmall, minlarge, maxval, maxres)
        segtree.set(a, maxval)

    return maxres




def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # nrows = int(inp[0])
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    nrows, k = list(map(int,inp[0].split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for n in range(nrows):
        grid.append(list(map(int,inp[n+1].split()))[0])

    res = solve(grid, k)  # please change
    
    # res = "\n".join(str(x) for x in res)
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

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

def main():
    



    
if __name__ == "__main__":
    main()

"""

import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, n, func, e, arrange=None):
        self.init(n)
        self.func = func
        self.e = e
        self.make_arrange(arrange)
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e]*(self.size)
            return
        self.segment = [0]*(self.N) + arrange + [self.e]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, 0, -1):
            self.segment[i] = self.func(self.segment[2*i], self.segment[2*i+1])
    
    def update(self, i, x):
        i += (self.N - 1)
        self.segment[i] = x
        while i > 1:
            i = i//2
            self.segment[i] = self.func(self.segment[2*i], self.segment[2*i+1])
    

    def count(self, l, r):
        res = self.e
        l += self.N-1
        r += self.N
        while r > l:
            if l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.func(res, self.segment[r])
            l >>= 1
            r >>= 1
        return res
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    def bisect_sub(self, a, b, k, l, r, x):
        if r <= a or b <= l:
            return b+1
        if self.segment[k] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+1, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 1, 0, self.size-self.N, x)

mod = 998244353

def main():
    n, k = map(int, input().split())
    a = [None]*n
    sub = 1
    e = 0
    func = max
    ma = 300001
    seg = SegmentTree(ma, func, e)
    ans = 0
    for i in range(n):
        a = int(input())
        sub = seg.count(max(0, a-k), min(a+k, ma)) + 1
        ans = max(ans, sub)
        seg.update(a, sub)
    
    print(ans)

main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
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
ide_ele = 0
b=[int(input()) for _ in range(N)]
c=max(b)
def segfunc(x,y):
    return max(x,y)
seg=SegTree([0]*(c+6),segfunc,ide_ele)
for i in range(N):
    a=b[i]
    seg.update(a,seg.query(max(0,a-K),min(c+2,a+K+1))+1)
print(seg.query(0,c+3))

Submission status: Accepted

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=[]
for i in range(N):
  A.append(int(input()))

N=300000
  
data = [0]*N
seg = SegTree(data, segfunc, ide_ele)

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.update(i,v+1)

print(seg.query(0,N))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

t = [[] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(ans-1, -1, -1):
        idx = bisect_left(t[j], A[i])
        if idx != len(t[j]):
            if abs(t[j][idx] - A[i]) <= K:
                t[j + 1].insert(bisect_left(t[j + 1], A[i]), A[i])
                ans = max(ans, j+2)
                break
        if idx > 0:
            if abs(t[j][idx-1] - A[i]) <= K:
                t[j + 1].insert(bisect_left(t[j + 1], A[i]), A[i])
                ans = max(ans, j+2)
                break
    else:
        t[0].insert(bisect_left(t[0], A[i]), A[i])
        ans = max(ans, 1)

print(ans)

Submission status: Accepted

Solution code:
# セグ木
# 使う操作
#####segfunc#####
def segfunc1(x, y):
    return max(x, y)
#################

#####ide_ele#####
ide_ele1 = -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())
low = [0]*(10**5 * 3 + 1)
seg = SegTree(low, segfunc1, ide_ele1)
for i in range(n):
    a = int(input())
    ma = seg.query(max(0,a-k), min(a+k+1,10**5 * 3 + 1))
    seg.update(a, ma+1)
ans = seg.query(0,10**5 * 3 + 1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.empty(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8, i8), cache=True)
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit((i8[:], i8, i8), cache=True)
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8[:], i8, i8), cache=True)
def max_right(seg, l, x):
    """[l,r) が ok であるような最大の r を返す"""
    N = len(seg) // 2

    def is_ok(v):
        return v < x

    v = None
    i, node_l, node_w = l + N, l, 1
    while True:
        if not (i & 1):
            i >>= 1
            node_w <<= 1
            continue
        if node_l + node_w > N:
            break
        v1 = seg_f(v, seg[i])
        if is_ok(v1):
            v, i = v1, (i + 1) >> 1
            node_l, node_w = node_l + node_w, node_w << 1
        else:
            break
    # 奇数セルに居て、とりきれないことが分かっている。偶数をとっていく
    i, node_w = i << 1, node_w >> 1
    while node_w:
        if node_l + node_w > N:
            i, node_w = i << 1, node_w >> 1
            continue
        v1 = seg_f(v, seg[i])
        if is_ok(v1):
            v, i = v1, (i + 1) << 1
            node_l, node_w = node_l + node_w, node_w >> 1
        else:
            i, node_w = i << 1, node_w >> 1
    i >>= 1
    return i - N

@njit((i8, i8[:]), cache=True)
def main(K, A):
    MAX = 300_010
    seg = np.zeros(2 * MAX, np.int64)
    for x in A:
        l, r = max(0, x - K), min(MAX, x + K + 1)
        n = fold(seg, l, r) + 1
        set_val(seg, x, n)
    return fold(seg, 0, MAX)

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(K, A))

Submission status: Accepted

Solution code:
N, K =map(int, input().split())
a = int(input())
M = a
m = a
ans = [[a]]
for _ in range(N - 1):
    a = int(input())
    if a > M+K or a < m-K:
        ans[0].append(a)
        M = max(M, a)
        m = min(m, a)
        continue
    M = max(M, a)
    m = min(m, a)
    j = 1
    check = 1
    while check:
        if j == len(ans)+1:
            ans[0].append(a)
            break
        for p in ans[-j]:
            if abs(p-a) <= K:
                if j == 1:
                    ans.append([a])
                else:
                    ans[-j+1].append(a)
                check = 0
                break
        j += 1
print(len(ans))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, op, e):
        self.n = 1 << (n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.n)

    def update(self, k, v):
        k += self.n
        self.data[k] = v
        while k > 0:
            k >>= 1
            self.data[k] = self.op(self.data[2 * k], self.data[2 * k + 1])

    def query(self, left, right):
        left += self.n
        right += self.n
        l_res = self.e
        r_res = self.e
        while left < right:
            if left & 1:
                l_res = self.op(l_res, self.data[left])
                left += 1
            left >>= 1
            if right & 1:
                right -= 1
                r_res = self.op(self.data[right], r_res)
            right >>= 1
        return self.op(l_res, r_res)


N, K, *A = map(int, open(0).read().split())
t = SegmentTree(650_000, max, 0)
ans = 0
for a in A:
    t.update(a, 1 + t.query(max(0, a - K), min(a + K, 300_000) + 1))
print(t.query(0, 300_001))