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: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    cnt = [0] * (n+1)
    for _ in range(n):
        a = int(input())
        m = max(cnt[max(a-k,0):min(a+k,n)+1])
        cnt[a] = m+1
    print(cnt[a])

main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input())
a = []
for i in range(n):
  if(i >= 1 and Math.abs(a[i-1] < a[i]) < k):
  a.push(int(input()))
print(a.length())

Submission status: Runtime Error

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), a+k+1)
    seg.update(a, ma+1)
ans = seg.query(0,10**5 * 3)
print(ans)

Submission status: Runtime Error

Solution code:
N, K = [int(n) for n in input().split(" ")]
A = []
for _ in range(N):
    A.append(int(input()))


D = [-1 for _ in range(300001)]
DD = []

ANS = -1

for n in range(N):
    maxd = -1
    for s in range(A[n] - K, A[n] + K + 1):
        if s < 0 or s > 300001:
            continue
        d = D[s] + 1
        if maxd <= d:
            maxd = d
    if maxd <= 0:
        maxd = 1
    D[A[n]] = maxd
    DD.append(maxd)

    if ANS <= maxd:
        ANS = maxd

print(ANS)

Submission status: Runtime Error

Solution code:

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    n, k = input_int_list()
    segtree = SegTree(300000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(300000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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, 0, LARGE)

    maxres = 0

    for a in arr:
        maxval = 0

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

        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: Runtime Error

Solution code:
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, 0, LARGE)

    maxres = 0

    for a in arr:
        maxval = 0

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

        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: Runtime Error

Solution code:
n,k=map(int, input().split())
a=[int(input()) for i in range(n)]
i,j=0,1
maxs=0
lis=[]
for i in range(n):
    cnt=1
    while i<n-1:
        if abs(a[i+j]-a[i])<=k:
            #lis.append(a[i+j])
            #print(lis)
            cnt+=1
            i+=j
            j=1
        else:
            j+=1
    maxs=max(maxs,cnt)
print(maxs)

Submission status: Runtime Error

Solution code:
class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [0] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

N,K = map(int,input().split())
ST = SegTree(300001)
for i in range(N):
    A = int(input())
    l = max(0,A-K)+1
    r = min(A+K,300000)+2
    M = ST.fold(l,r)
    ST.set_val(A+1,M+1)
print(ST.X[1])

Submission status: Runtime Error

Solution code:
tmpn,k=map(int,input().split())
a=[int(input()) for _ in range(tmpn)]
n=3*10**5+2

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = 0

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max([0]*n)

for aa in a:
    aa+=1
    maxlen=query_max(aa-k,aa+k+1)
    update_max(aa,maxlen+1)

print(query_max(0,n+1))

Submission status: Runtime Error

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

def main():
    n, k = map(int, input().split())
    alst = [int(input()) for _ in range(n)]
    N = max(alst) + 1
    
    INF = 0
    
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)
    
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None
    
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
    
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                xx = max(data[R-1], x)
                if lazy[R-1] != None:
                    xx = max(xx, lazy[R-1])
                lazy[R-1] = data[R-1] = max(data[R-1], xx)
            if L & 1:
                xx = max(data[R-1], x)
                if lazy[L-1] != None:
                    xx = max(xx, lazy[L-1])
                lazy[L-1] = data[L-1] = max(data[L-1], xx)
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = max(data[2*i-1], data[2*i])
    
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r
    
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, data[R-1])
            if L & 1:
                s = max(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    ans = 0
    for a in alst:
        l = a - k
        r = a + k
        x = query(a, a + 1) + 1
        update(l, r + 1, x)
        ans = max(ans, x)
    print(ans)
    
main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [int(input()) for i in range(5)]

ans = 1

i = 1
while( i <= N-2 ):
  if ( abs(A[i]-A[i+1]) <= K ):
    ans += 1
  i += 1
  
print(ans)

Submission status: Runtime Error

Solution code:
class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        if q:
            self._lazy[2 * idx] = max(self._lazy[2 * idx],q)
            self._lazy[2 * idx + 1] = max(self._lazy[2 * idx + 1],q)
            self.data[2 * idx] = max(self.data[2 * idx], q)
            self.data[2 * idx + 1] = max(self.data[2 * idx + 1], q)

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = max(self.data[idx], self._func(self.data[2 * idx], self.data[2 * idx + 1]))
            self._push(idx)
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            #print('a', start, stop)
            if start & 1:
                self._lazy[start] = max(self._lazy[start], value)
                self.data[start] = max(self.data[start],value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = max(self._lazy[stop], value)
                self.data[stop] = max(self.data[stop],value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
seg = LazySegmentTree([0] * (65536))
for _ in range(n):
    v = int(input())
    most = seg.query(v, v+1)
    #print(most)
    seg.add(max(0,v - k), v + k + 1, most + 1)
    #print(seg.data)
print(seg.query(0, 65536))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**7)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()

N = n

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = 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):
    a = ni()
    s = a-k-1 if a-k-1 > 0 else 0
    e = a+k-1 if a+k < n else n
    update(a-1, query(s,e)-1)


print(-query(0,n)+1)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()

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

ide_ele = -1

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

seg = SegTree([0]*N, segfunc, ide_ele)
for _ in range(N):
    a = int(input())
    maxi = seg.query(max(0, a-K-1), min(N, a+K))
    seg.update(a-1, maxi+1)
print(seg.query(0, N))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = [int(input()) for _ in range(10)]
s = set()
ans = 0
for i in range(n):
  cnt = 1
  tmp = a[i]
  for j in range(i+1,n):
    if j in s:
      break
    if abs(a[j]-tmp)<=k:
      cnt += 1
      tmp = a[j]
      s.add(j)
  ans = max(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import os

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


def input():
    return sys.stdin.readline().rstrip()


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

    A = []
    for i in range(n):
        A.append(int(input()))

    for i in range(len(A) - 1):
        a = A[i]
        b = A[i + 1]
        if a == -1:
            continue
        if i == len(A) - 1 - 1:
            if abs(b - a) > k:
                A[i + 1] = -1

        c = A[i + 2]
        if abs(b - a) > k:
            if abs(c - a) <= k:
                A[i + 1] = -1
            elif abs(c - b) <= k:
                A[i] = -1
            else:
                A[i] = A[i + 1] = -1

    ans = 0

    for a in A:
        if a != -1:
            ans += 1

    print(ans)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for j in dic[a]:
                    if mark[j]:
                        continue
                    
                    d.appendleft(j)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
#a = list(map(int, input().split()))
cnt = [0]*(n+1)

for _ in range(n):
    a = int(input())
    cnt[a] = max(cnt[max(0,a-k):min(n,a+k+1)])+1

print(max(cnt))

Submission status: Runtime Error

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

if (len(a) == 1):
  print(1)
  exit()
if (len(a) == 2):
  if abs(a[0] - a[1])  > k:
    print(1)
  else:
    print(2)
  exit()
ch = 0
while (ch < len(a)):
  #print(a,ch)
  if abs(a[ch] - a[ch+1])  > k:
    a.pop(ch+1)
    ch -= 1
  ch += 1

print(len(a),ch)

Submission status: Runtime Error

Solution code:
#k = int(input())
n,k = map(int, input().split())
#a = list(map(int, input().split()))
cnt = [0]*(n+1)

for _ in range(n):
    a = int(input())
    cnt[a] = max(cnt[max(0,a-k):min(n,a+k+1)])+1

print(max(cnt))

Submission status: Runtime Error

Solution code:
def rec(pos, a, dp, n, k):
    if dp[pos] != -1:
        return dp[pos]
    for nxt in range(pos + 1, n):
        if abs(a[pos] - a[nxt]) <= k:
            dp[pos] = rec(nxt, a, dp, n, k) + 1
            return dp[pos]
    dp[pos] = 1
    return 1


def acl_beginner_d():
    n, k = map(int, input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    dp = [-1] * n
    ans = -float('inf')
    for i in range(n):
        ans = max(ans, rec(i, a, dp, n, k))
    print(ans)


acl_beginner_d()

Submission status: Runtime Error

Solution code:
#from collections import deque, Counter
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#from decimal import Decimal
#mod = 1000000007
#mod = 998244353
#N = int(input())
#####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



### https://qiita.com/ell/items/fe52a9eb9499b7060ed6 heapについて　最大最小の取り出し
N, K = map(int, input().split())
tree = [0 for _ in range(N)]
tree = SegTree(tree, segfunc, ide_ele)
for k in range(N):
  A = int(input())
  A -= 1
  n = tree.query(max(0, A-K), min(N-1, A+K)+1)
  tree.update(A, n+1)
print(tree.query(0, N))
#A = list(map(int, input().split()))
#flag = True
#for k in range(N):
#ans = 0
#print(ans)
#print('Yes')
#print('No')

Submission status: Runtime Error

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

list_a = []
for _ in range(n):
     list_a.append(int(input()))
        
memo = dict()


def subilst_max_length(current_value, i):
    if (current_value, i) in memo.keys():
        return memo[(current_value, i)]
    if i == n-1:
        if abs(current_value - list_a[i]) <= k:
            memo[(current_value, i)] = 1
            return 1
        memo[(current_value, i)] = 0
        return 0
    if abs(current_value - list_a[i]) <= k:
        # iの値をsublistに含めるor含めない
        memo[(current_value, i)] = max(1+subilst_max_length(list_a[i], i+1), subilst_max_length(current_value, i+1))
        return memo[(current_value, i)]
    memo[(current_value, i)] = subilst_max_length(current_value, i+1)
    return memo[(current_value, i)]
  
print(subilst_max_length(list_a[0], 0))

Submission status: Runtime Error

Solution code:
A = []
for i in range(N):
  A.append(int(input()))

B = []
for j in range(N):
  B.append(1)

for j in range(N):
  for k in range(j):
    if A[N-j-1] <= A[N-k-1] and A[N-k-1] -  A[N-j-1] <= K:
      B[N-j-1] = max(B[N-j-1], B[N-k-1] + 1)
    elif A[N-k-1] < A[N-j-1] and A[N-j-1] - A[N-k-1] <= K:
      B[N-j-1] = max(B[N-j-1], B[N-k-1] + 1)
print(max(B))