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 segment_tree:
    __slots__ = ["op_M", "e_M","N","N0","dat"]
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        self.N = N
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        assert self.N == len(initial)
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k >>= 1

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]
    
    """
    f(x_l*...*x_{r-1}) が True になる最大の r 
    つまり TTTTFFFF となるとき、F となる最小の添え字
    存在しない場合 n が返る
    f(e_M) = True でないと壊れる
    """
    def max_right(self,l,f):
        if l == self.N: return self.N;
        l += self.N0
        sm = self.e_M
        while True:
            while l&1==0:
                l >>= 1
            
            if not f(self.op_M(sm,self.dat[l])):
                while l < self.N0:
                    l *= 2
                    if f(self.op_M(sm,self.dat[l])):
                        sm = self.op_M(sm,self.dat[l])
                        l += 1
                return l - self.N0

            sm = self.op_M(sm,self.dat[l])
            l += 1
            if (l & -l) == l: break
        
        return self.N

    """
    f(x_l*...*x_{r-1}) が True になる最小の l
    つまり FFFFTTTT となるとき、T となる最小の添え字
    存在しない場合 r が返る
    f(e_M) = True でないと壊れる
    """
    def min_left(self,r,f):
        if r == 0: return 0
        r += self.N0
        sm = self.e_M
        
        while True:
            r -= 1
            while r > 1 and r&1:
                r >>= 1

            if not f(self.op_M(self.dat[r],sm)):
                while r < self.N0:
                    r = r*2 + 1
                    if f(self.op_M(self.dat[r],sm)):
                        sm = self.op_M(self.dat[r],sm)
                        r -= 1
                return r + 1 - self.N0

            sm = self.op_M(self.dat[r],sm)
            if (r & -r) == r: break

        return 0


###########################################################################
# https://atcoder.jp/contests/practice2/submissions/16767822
###########################################################################
import sys
readline = sys.stdin.readline

n,k = map(int, readline().split())
#*a, = map(int, readline().split())
M = 3*10**5+5
seg = segment_tree(M,max,0)
#seg.build(a)

for _ in range(n):
    a = int(readline())
    v = seg.query(max(0,a-k),min(M,a+k))
    seg.update(a,v+1)

print(seg.dat[1])

Submission status: Accepted

Solution code:
N, K, *A = [int(_) for _ in open(0).read().split()]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([0] * 300001, max, 0)
for a in A:
    l = max(0, a - K)
    r = min(a + K, 300000)
    st.update(a, st.query(l, r + 1) + 1)
print(st.query(0, 300001))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res
MAX=max(A)+1
s=SegmentTree(MAX,lambda a,b: max(a,b),0)

s.update(A[0],1)
ans=1

for x in A[1:]:
    p=max(x-K,0)
    q=min(x+K+1,MAX)
    res=s.query(p,q)
    s.update(x,res+1)
    ans=max(ans,res+1)
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=max, ident=-2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

        # return smallest i(l <= i < r) s.t. check(A[i]) == True
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1

    N, K = map(int, input().split())
    ST = SegmentTree([0] * 300010)
    for _ in range(N):
        a = int(input())
        ST.update(a + 1, ST.query(max(1, a - K + 1), min(300010, a + K + 2)) + 1)
    print(ST.data[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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


class SegmentTree:
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    build(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def build(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)

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

ans = 0
st = SegmentTree(max_a + 1, max, 0)
ans = 0
for val in a:
    l, r = max(val - k, 0), min(val + k + 1, max_a + 1)
    res = st.get_val(l, r)
    ans = max(res, ans)
    st.update(val, res + 1)
print(ans + 1)

Submission status: Accepted

Solution code:

class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。(ただし単位元は添加可能)
    """
    @classmethod
    def all_identity(cls, operator, identity, size):
        return cls(operator, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, identity, data):
        self.op = operator
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        while i:
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

L = 300000
N,K = map(int,readline().split())
seg = SegmentTree.all_identity(max2, 0, L+1)

for a in map(int,read().split()):
    seg[a] = seg[max2(0,a-K):min2(L,a+K)+1]+1

print(seg[:])

Submission status: Accepted

Solution code:

#0-indexed , 半開区間[a,b)
#calc変更で演算変更
class SegTree:

    def __init__(self,N,first):
        self.NO = 2**(N-1).bit_length()
        self.First = first
        self.data = [first] * (2*self.NO)

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

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

    def query(self,l,r):
        L = l + self.NO
        R = r + self.NO
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s , self.data[R-1])
            if L & 1:
                s = self.calc(s , self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self , ind):
        ind += self.NO - 1
        return self.data[ind]

from sys import stdin

N,K = map(int,stdin.readline().split())

ST = SegTree(400000,0)

for i in range(N):

    A = int(stdin.readline())

    nmax = ST.query(max(0,A-K) , min(350000,A+K+1))
    ST.update(A,nmax+1)

print (ST.query(0,350000))

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, size, op, I):
        n = 1
        while n < size:
            n <<= 1
        self.size = n
        self.op = op
        self.I = I
        self.node = [I] * (2 * n)

    def __getitem__(self, k):
        return self.node[k + self.size]

    def build(self, v):
        for k in range(len(v)):
            self.node[k + self.size] = v[k]
        for k in range(self.size - 1, 0, -1):
            self.node[k] = self.op(self.node[2 * k], self.node[2 * k + 1])

    def update(self, k, x):
        k += self.size
        self.node[k] = x
        while k > 1:
            k >>= 1
            self.node[k] = self.op(self.node[2 * k], self.node[2 * k + 1])

    def query(self, l, r):
        vl = vr = self.I
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                vl = self.op(vl, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.op(self.node[r], vr)
            l >>= 1
            r >>= 1
        return self.op(vl, vr)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
M = 300000
st = SegmentTree(M + 1, max, 0)
for i in range(N):
    a = A[i]
    x = st.query(max(0, a - K), min(a + K, M) + 1)
    st.update(a, x + 1)
print(st.query(0, M + 1))

Submission status: Accepted

Solution code:
class SegmentTree:

    __slots__ = ["func", "e", "n", "data"]

    def __init__(self, monoid_data, func, e):
        self.func = func
        self.e = e
        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def __getitem__(self, index):
        return self.data[self.n + index]

import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

N, K = map(int, input().split())
As = list(map(int, read().split()))

dp = SegmentTree([0] * 300001, max, 0)
for A in As:
    l = max(0, A - K)
    r = min(300001, A + K + 1)
    dp.replace(A, dp.folded(l, r) + 1)

print(dp.folded(0, 300001))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class SegmentTree:
    def __init__(self, size, f=max, default=0):
        self.size = 2**(size-1).bit_length()
        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 get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + 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
def solve():
    n,k = LI()
    a = IR(n)
    m = max(a)
    s = SegmentTree(m+1)
    ans = 1

    for i in a:
        l = max(0,i-k)
        r = min(m+1,i+k+1)
        p = s.get(l,r)+1
        s.update(i,p)
        if ans < p:
            ans = p
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


n,k = map(int, input().split())
seg = SegmentTree([0]*(400000))
for _ in range(n):
    a = int(input())
    ma = seg.get_segment(max(0, a-k), min(400000,a+k+1))
    seg.update_func(a,ma+1)
print(seg.get_segment(0, 400000))

Submission status: Accepted

Solution code:
class SegmentTree:
    #for pypy
    #treeは1-based-index,queryは0-based-index
    __slots__=["size","func","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,func,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.func=func#適用関数
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            self.tree[self.size+i]=initial_value_list[i]
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.func(self.tree[2*k],self.tree[2*k+1])
    def query(self, l, r):
        #res->func[l,r)
        l+=self.size-self.first_idx
        r+=self.size-self.first_idx
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=self.func(lret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rret=self.func(self.tree[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return self.func(lret, rret)
n,k=map(int,input().split())
MAX=300050
seg=SegmentTree([0]*300050,max,0,0)
for _ in range(n):
    a=int(input())
    seg.update(a,seg.query(max(a-k,0),min(MAX,a+k)+1)+1)
print(seg.query(0,MAX))

Submission status: Accepted

Solution code:
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,K=map(int,input().split())
A=0
X=[]
init(300001,X,0,lambda x,y:max(x,y))
for i in range(N):
  A=int(input())
  upd(X,A,query(X,max(0,A-K),min(300001,A+K+1))+1)
print(X[0])

Submission status: Accepted

Solution code:
# SegmentTree
class SegmentTree:
  def __init__(self, n, p, unit, f):
    self.num = 2**((n-1).bit_length())
    self.seg = [unit]*(2*self.num)
    for i in range(n):
      self.seg[i+self.num] = p[i]
    for i in range(self.num-1, 0, -1):
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
    self.f = f
    self.unit = unit

  def update(self, i, x):
    i += self.num
    self.seg[i] = x
    while i:
      i >>= 1
      self.seg[i] = self.f(self.seg[i << 1], self.seg[(i << 1)+1])

  def query(self, l, r):
    ansl = ansr = self.unit
    l += self.num
    r += self.num-1
    if l == r:
      return self.seg[l]
    while l < r:
      if l & 1:
        ansl = self.f(ansl, self.seg[l])
        l += 1
      if ~r & 1:
        ansr = self.f(self.seg[r], ansr)
        r -= 1
      l >>= 1
      r >>= 1
    if l == r:
      ansl = self.f(ansl, self.seg[l])
    return self.f(ansl, ansr)

n,k=map(int,input().split())
a=[int(input())for _ in range(n)]
m=max(a)
seg=SegmentTree(m,[0]*m,0,lambda x,y: max(x,y))
ans=0
for x in a:
  f=seg.query(max(0,x-k),min(m,x+k)+1)
  seg.update(x,f+1)
  ans=max(ans,f+1)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=list(map(int,input().split()))
a=[int(input()) for i in range(n)]
import sys
sys.setrecursionlimit(10**7)
#ide_ele:単位元を設定
ide_ele=-float("INF")
#segfunc:演算を定義
def segfunc(x,y):
  return max(x,y)
#num:n以上の最小の2のべき乗
#seg:セグメンテーション木
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
#init:引数を初期化する
def init(init_val):
  for i in range(n):
    seg[i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
#update(a,b):init[a]の値をbに更新したときどうなるか
def update(k,x):
  k+=num-1
  seg[k]=x
  while k>0:
    k=(k-1)//2
    seg[k]=segfunc(seg[2*k+1],seg[2*k+2])
#query(p,q):[p,q)についてsegfuncしたものを返す
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%2==0:
      res=segfunc(res,seg[p])
      p=p+1
    if q%2==1:
      res=segfunc(res,seg[q])
      q=q-1
    p=(p-1)//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[p])
  else:
    res=segfunc(segfunc(res,seg[p]),seg[q])
  return res
 
maxa=max(a)
dp=[0]*(maxa++2)
init(dp)
for i in range(n):
  if a[i]+k-1>maxa:
    dp[a[i]]=query(a[i]-k,maxa)+1
    update(a[i],dp[a[i]])
  elif a[i]-k<0:
    dp[a[i]]=query(0,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  else:
    dp[a[i]]=query(a[i]-k,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  
  
print(max(dp))

Submission status: Runtime Error

Solution code:
n,k=list(map(int,input().split()))
a=[int(input()) for i in range(n)]
import sys
sys.setrecursionlimit(10**7)
#ide_ele:単位元を設定
ide_ele=-float("INF")
#segfunc:演算を定義
def segfunc(x,y):
  return max(x,y)
#num:n以上の最小の2のべき乗
#seg:セグメンテーション木
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
#init:引数を初期化する
def init(init_val):
  for i in range(n):
    seg[i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
#update(a,b):init[a]の値をbに更新したときどうなるか
def update(k,x):
  k+=num-1
  seg[k]=x
  while k>0:
    k=(k-1)//2
    seg[k]=segfunc(seg[2*k+1],seg[2*k+2])
#query(p,q):[p,q)についてsegfuncしたものを返す
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%2==0:
      res=segfunc(res,seg[p])
      p=p+1
    if q%2==1:
      res=segfunc(res,seg[q])
      q=q-1
    p=(p-1)//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[p])
  else:
    res=segfunc(segfunc(res,seg[p]),seg[q])
  return res
 
maxa=max(a)
dp=[0]*(maxa+1)
init(dp)
for i in range(n):
  if a[i]+k-1>maxa:
    dp[a[i]]=query(a[i]-k,maxa)+1
    update(a[i],dp[a[i]])
  elif a[i]-k<0:
    dp[a[i]]=query(0,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  else:
    dp[a[i]]=query(a[i]-k,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  
 
print(max(dp))

Submission status: Runtime Error

Solution code:
n,k=list(map(int,input().split()))
a=[int(input()) for i in range(n)]
 import sys
sys.setrecursionlimit(10**7)
#ide_ele:単位元を設定
ide_ele=-float("INF")
#segfunc:演算を定義
def segfunc(x,y):
  return max(x,y)
#num:n以上の最小の2のべき乗
#seg:セグメンテーション木
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
#init:引数を初期化する
def init(init_val):
  for i in range(n):
    seg[i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
#update(a,b):init[a]の値をbに更新したときどうなるか
def update(k,x):
  k+=num-1
  seg[k]=x
  while k>0:
    k=(k-1)//2
    seg[k]=segfunc(seg[2*k+1],seg[2*k+2])
#query(p,q):[p,q)についてsegfuncしたものを返す
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%2==0:
      res=segfunc(res,seg[p])
      p=p+1
    if q%2==1:
      res=segfunc(res,seg[q])
      q=q-1
    p=(p-1)//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[p])
  else:
    res=segfunc(segfunc(res,seg[p]),seg[q])
  return res
 
maxa=max(a)
dp=[0]*(maxa+1)
init(dp)
for i in range(n):
  if a[i]+k-1>maxa:
    dp[a[i]]=query(a[i]-k,maxa)+1
    update(a[i],dp[a[i]])
  elif a[i]-k<0:
    dp[a[i]]=query(0,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  else:
    dp[a[i]]=query(a[i]-k,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  
 
print(max(dp))

Submission status: Runtime Error

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

#ide_ele:単位元を設定
ide_ele=-float("INF")
#segfunc:演算を定義
def segfunc(x,y):
  return max(x,y)
#num:n以上の最小の2のべき乗
#seg:セグメンテーション木
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
#init:引数を初期化する
def init(init_val):
  for i in range(n):
    seg[i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
#update(a,b):init[a]の値をbに更新したときどうなるか
def update(k,x):
  k+=num-1
  seg[k]=x
  while k>0:
    k=(k-1)//2
    seg[k]=segfunc(seg[2*k+1],seg[2*k+2])
#query(p,q):[p,q)についてsegfuncしたものを返す
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%2==0:
      res=segfunc(res,seg[p])
      p=p+1
    if q%2==1:
      res=segfunc(res,seg[q])
      q=q-1
    p=(p-1)//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[p])
  else:
    res=segfunc(segfunc(res,seg[p]),seg[q])
  return res

maxa=max(a)
dp=[0]*(maxa+1)
init(dp)
for i in range(n):
  if a[i]+k-1>maxa:
    dp[a[i]]=query(a[i]-k,maxa)+1
    update(a[i],dp[a[i]])
  elif a[i]-k<0:
    dp[a[i]]=query(0,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  else:
    dp[a[i]]=query(a[i]-k,a[i]+k+1)+1
    update(a[i],dp[a[i]])
  

print(max(dp))