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:
#####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
# coding: utf-8
# Your code here!
a = input().split()
N = int(a[0])
M = int(a[1])
a = []
k = [int(input()) for i in range(N)]

temp = int(0)

for i in range(300001):
    a.append(0)
    
seg = SegTree(a, segfunc, ide_ele)

for i in range(N):
    temp = seg.query(max(0, k[i]-M), k[i]+M+1)
    seg.update(k[i], temp+1)

print(seg.query(0,300001))

Submission status: Runtime Error

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
# coding: utf-8
# Your code here!
a = input().split()
N = int(a[0])
M = int(a[1])
d = {}
最初 = []
k = [int(input()) for i in range(N)]
k.reverse()
temp = int(0)

for i in range(300001):
    最初.append(0)
    
seg = SegTree(最初, segfunc, ide_ele)

for i in range(N):
    temp = seg.query(max(0, k[i]-M), k[i]+M+1)
    seg.update(k[i], temp+1)

print(seg.query(k[N-1],k[N-1]+1))

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, lis, ele, op):
        self.len = len(lis)
        self.n = 1 << ((self.len - 1).bit_length())
        self.op = op
        self.ele = ele
        self.tree = self._build(lis)
    def _build(self, lis):
        res_tree = [self.ele] * (self.n - 1) + lis + [self.ele] * (self.n - self.len)
        for i in range(self.n - 2, -1, -1):
            res_tree[i] = self.op(res_tree[i * 2 + 1], res_tree[i * 2 + 2])
        return res_tree
    def __get__(self, i):
        return self.tree[self.n + i - 1]
    def update(self, i, x):
        i += self.n - 1
        self.tree[i] = x
        while i > 0:
            i -= 1
            i >>= 1
            self.tree[i] = self.op(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    def query(self, l, r):
        l +=  self.n - 1
        r += self.n - 1
        L = self.ele
        R = self.ele
        while l < r:
            if l & 1 == 0:
                L = self.op(L, self.tree[l])
                l += 1
            if r & 1 == 0:
                r -= 1
                R = self.op(R, self.tree[r])
            l -= 1
            l >>= 1
            r >>= 1
        return self.op(L, R)
n, k = map(int, input().split())
ST = SegmentTree([0] * 200000, 0, max)
for i in range(n):
    a = int(input())
    res = ST.query(max(0, a - k), min(200000, a + k + 1))
    ST.update(a, res + 1)
print(ST.tree[1])

Submission status: Runtime Error

Solution code:
from typing import Callable, TypeVar, List

T = TypeVar('T')


class SegTree:
    def __init__(self, v: List[T], op: Callable[[T, T], T], e: Callable[[], T]) -> None:
        self._n = len(v)
        self.log = (self._n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e() for _ in range(2 * self.size)]
        self.op = op
        self.e = e
        for i in range(self._n):
            self.d[self.size + i] = v[i]
        for i in reversed(range(1, self.size)):
            self.__update__(i)

    @classmethod
    def init_e(cls, n: int, op: Callable[[T, T], T], e: Callable[[], T]) -> 'SegTree':
        return cls([e() for _ in range(n)], op, e)

    def set(self, p: int, x: T) -> 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) -> T:
        assert 0 <= p < self._n
        return self.d[p + self.size]

    def prod(self, l: int, r: int) -> T:
        assert 0 <= l <= self._n and 0 <= r <= self._n
        sml = self.e()
        smr = self.e()
        l += self.size
        r += self.size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self) -> T:
        return self.d[1]

    def max_right(self, l: int, f: Callable[[T], bool]):
        assert 0 <= l <= self._n
        assert f(self.e())
        if l == self._n:
            return self._n
        l += self.size
        sm = self.e()
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l *= 2
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                return self._n

    def min_left(self, r: int, f: Callable[[T], bool]):
        assert 0 <= r <= self._n
        assert f(self.e())
        if r == 0:
            return 0
        r += self.size
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                return 0

    def __update__(self, k: int) -> None:
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])


n, k = map(int, input().split())
seg = SegTree([0]*40000, max, lambda: 0)
for _ in range(n):
    a = int(input())
    ma = seg.prod(max(0, a-k), min(400000, a+k+1))
    seg.set(a, ma+1)
print(seg.all_prod())

Submission status: Runtime Error

Solution code:
import math

N, K = map(int, input().split())
Amax = 300000
# seg_leaf : seg_tree の葉で [0:0) に当たるノードのインデックス
seg_leaf_0 = 2**int(math.log2(Amax+1))
# seg_tree : 1-indexed のセグ木
seg_tree = [0]*(seg_leaf_0 * 2)

def get_max(check_min, check_max, area_min, area_max, node_ind):
    if area_max < check_min or check_max < area_min:
        return 0
    elif check_min <= area_min and area_max <= check_max:
        return seg_tree[node_ind]
    else:
        v1 = get_max(check_min, check_max, area_min, (area_min + area_max)//2, node_ind * 2)
        v2 = get_max(check_min, check_max, (area_min + area_max)//2 + 1, area_max, node_ind * 2 + 1)
        return(max(v1, v2))

def update(node_ind, value):
    seg_tree[node_ind] = value
    if node_ind != 1:
        update(node_ind//2, value)

for _ in range(N):
    A = int(input())
    x = get_max(max(A-K, 0), min(A+K, Amax), 0, seg_leaf_0 * 2 - 1, 1)
    update(seg_leaf_0 + A, x + 1)

print(seg_tree[1])

Submission status: Runtime Error

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/atcoder-stl
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/segtree>" namespace "atcoder" nogil:
    cdef cppclass segtree[S, OP, E]:
        segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        int max_right[F](int l)
        int min_left[F](int r)
ctypedef long seg_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int f_t "myf"
    cdef seg_t myop(seg_t a, seg_t b) nogil
    cdef seg_t mye() nogil
    cdef bool myf(seg_t k) nogil
cdef seg_t myop(seg_t a, seg_t b) nogil:
    if a > b:
        return a
    else:
        return b
cdef seg_t mye() nogil:
    return 0
cdef seg_t v
cdef bool myf(seg_t k) nogil:
    return k < v

from cython.parallel cimport prange
from libc.stdio cimport getchar, printf
cdef inline long read() nogil:
    cdef long b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef main():
    cdef long n = read(), k = read(), i
    cdef seg_t a
    cdef segtree[seg_t, op_t, e_t] *seg = new segtree[seg_t, op_t, e_t](vector[seg_t](600001, 0))
    for i in range(n):
        a = read()
        seg.set(a, seg.prod(myop(0, a - k), a + k + 1) + 1)
    printf('%ld\n', seg.all_prod())
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

Solution code:
import math

N, K = map(int, input().split())
Amax = 300000
# seg_leaf : seg_tree の葉で [0:0} に当たるノードのインデックス
seg_leaf_0 = 2**int(math.log2(Amax+1))
# seg_tree : 1-indexed のセグ木
seg_tree = [0]*(seg_leaf_0 * 2)

def get_max(check_min, check_max, area_min, area_max, node_ind):
    if area_max < check_min or check_max < area_min:
        return 0
    elif check_min <= area_min or area_max < check_max:
        return seg_tree[node_ind]
    else:
        v1 = get_max(check_min, check_max, area_min, (area_min + area_max)//2, node_ind * 2)
        v2 = get_max(check_min, check_max, (area_min + area_max)//2 + 1, area_max, node_ind * 2 + 1)
        return(max(v1, v2))

def update(node_ind, value):
    seg_tree[node_ind] = value
    if node_ind != 1:
        update(node_ind//2, value)

for _ in range(N):
    A = int(input())
    x = get_max(max(A-K, 0), min(A+K, Amax), 0, seg_leaf_0 * 2 - 1, 1)
    update(seg_leaf_0 + A, x + 1)

print(seg_tree[1])

Submission status: Runtime Error

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, K, A):
    tree = SegmentTree(300_300)
    for a in A:
        p = tree.query(a - K, a + K + 1)
        tree.modify(a, p + 1)
    print(tree.query(0, 300_300))

class SegmentTree:
    __slots__ = ('__n', '__d', '__f', '__e')

    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i], i = new_value, i >> 1
        while i: d[i], i = f(d[i << 1], d[i << 1 | 1]), i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, j, n, f, d, v = self.__n, self.__n + self.__n, self.__n, self.__f, self.__d, self.__e()
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv): break
                v, i = nv, i + 1
            i, j = i >> 1, j >> 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv): v, i = nv, i << 1 | 1
            else: i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    main(N, K, A)

Submission status: Runtime Error

Solution code:
import numpy

l = input().split(' ')
N = int(l[0])
K = int(l[1])
A = []
for i in range(N):
  A.append(int(input()))

dp = [-1]*(N+1)
dp[0] = 0

for i in range(N):
  flg = False
  n = numpy.amax(dp)
  #print('a'+str(n))
  for j in range(n,-1,-1):
    arr = [k for k, x in enumerate(dp) if x == j]
    #print(arr)
    for k in range(len(arr)):
      if(abs(A[i]-A[arr[k]])<=K):
        dp[i] = dp[arr[k]]+1
        flg = True
        break
    if(flg):
      break

print(numpy.max(dp))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# Date [ 2020-09-26 21:43:42 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys

def read_str(): return sys.stdin.readline().strip()
def read_int(): return int(sys.stdin.readline().strip())
def read_ints(): return map(int, sys.stdin.readline().strip().split())
def read_str_split(): return list(sys.stdin.readline().strip())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))

class segtree:
    def __init__(self, op, e, v: list):
        self._n = len(v)
        self.log = ceil_pow2(self._n)
        self.size = 1 << self.log
        self.op = op; self.e = e
        self.d = [self.e()] * (self.size * 2)
        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: int):
        assert 0 <= p and 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):
        assert 0 <= p and p < self._n
        return self.d[p + self.size]

    def prod(self, l: int, r: int):
        assert 0 <= l and l <= r and r <= self._n
        l += self.size; r += self.size
        sml, smr = self.e(), self.e()
        while l < r:
            if l & 1: sml = self.op(sml, self.d[l]); l += 1
            if r & 1: r -= 1; smr = self.op(self.d[r], smr)
            l >>= 1; r >>= 1
        return self.op(sml, smr)

    def all_prod(self): return self.d[1]

    def max_right(self, l: int, f):
        assert 0 <= l and l <= self._n
        assert f(self.e())
        if l == self._n: return self._n
        l += self.size
        sm = self.e()
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: break
        return self._n

    def min_left(self, r: int, f):
        assert 0 <= r and r <= self._n
        assert f(self.e())
        if r == 0: return 0
        r += self.size
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: break
        return 0

    def __update(self, k: int): self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

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

def op(a, b): return max(a, b)
def e(): return 0

def Main():
    n, k = read_ints()
    A = [read_int() for _ in range(n)]
    seg = segtree(op, e, [0] * n)
    seg.set_(A[0], 1)
    for i in range(1, n):
        seg.set_(A[i], seg.prod(max(A[i] - k, 0), min(A[i] + k + 1, seg._n)) + 1)
    print(seg.prod(0, seg._n))

if __name__ == '__main__':
    Main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-N), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)

seg = SegTree(N+1,max,0)
seg.build([0]*(N+1))
A=[int(input()) for _ in range(N)]
for i in range(N):
  a = A[i]
  tmp = seg.fold(max(0,a-K),min(N,a+K+1))
  seg.set_val(a,tmp+1)

print(seg.fold(0,N))

Submission status: Runtime Error

Solution code:
import sys
z=sys.stdin.readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        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 __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
 
n,k=map(int,z().split())
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(z())
    s[a]=1+s.query(max(0,a-k),min(a+k+1,M))
print(s.query(0,300001))

Submission status: Runtime Error

Solution code:
import sys
z=sys.stdin.readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        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 __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
 
n,k=map(int,z().split())
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(max(0,a-k),min(a+k+1,M))
print(s.query(0,300001))

Submission status: Runtime Error

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


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

st = SegmentTree([N] * (max(A) + 1), min, N)
edge = [set() for _ in range(N)]
for i, a in enumerate(reversed(A)):
    j = N - 1 - i
    p1 = st.get(a + 1, a + K + 1)
    if p1 != N:
        edge[j].add(p1)
    p2 = st.get(max(0, a - K), a)
    if p2 != N:
        edge[j].add(p2)
    p0 = st.get(a, a + 1)
    if p0 != j and p0 != N:
        edge[j].add(p0)
    st.update(a, j)

dp = [0] * N
dp[0] = 1
for i in range(N - 1):
    here = dp[i]
    for ni in edge[i]:
        if ni < N:
            dp[ni] = max(dp[ni], dp[i] + 1)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
z=sys.stdin.readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        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 __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
 
n,k=map(int,z().split())
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(a-k,a+k+1)
print(s.query(0,300001))

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())

notcalled=list(range(1,N+1))
nets=[]
for _ in range(M):
    a,b=map(int, input().split())
    if a in notcalled and b in notcalled:
        nets.append([a,b])
        del notcalled[notcalled.index(a)]
        del notcalled[notcalled.index(b)]
    elif a in notcalled:
        for net in nets:
            if b in net:
                net.append(a)
        del notcalled[notcalled.index(a)]
    elif b in notcalled:
        for net in nets:
            if a in net:
                net.append(b)
        del notcalled[notcalled.index(b)]
    else:
        for net in nets:
            f=True
            if a in net or b in net:
                if f:
                    q=net.copy
                    del net
                else:
                    net.extend(q)

print(len(nets)-1+len(notcalled))

Submission status: Runtime Error

Solution code:
import sys,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        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 __delitem__(self, idx):
        self[idx] = self._default
    def __getitem__(self, idx):
        return self.data[idx + self._size]
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
    def __len__(self):
        return self._len
    def query(self, start, stop):
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
 
n,k=map(int,z().split())
s=SegmentTree([0]*300001)
for i in range(n):
    a=int(input())
    s[a]=1+s.query(a-k,a+k+1)
print(s.query(0,300001))