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:
#!/usr/bin/env python3
class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        self.tree[self.size :self.size + self.n] = v
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x

        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

    def all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

MAX_A = 300005

dp = SegTree(max, 0, 100, 0)
for i in range(N):
    x = A[i]
    now = dp.query(max(0, x - K), min(x + K + 1, MAX_A)) + 1
    dp.set(x, now)

ans = dp.all_query()
print(ans)

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

def resolve():
  N, K = map(int, input().split(" "))
  max_range = (9 + 1)
  dp = [0] * max_range
  seg = SegTree(dp, segfunc, ide_ele)

  for _ in range(N):
    A = int(input())
    left = A-K
    right = A+K+1 #半開区間なので +1 してる
    seg.update(A, seg.query(left, right) + 1)

  print(seg.query(0, max_range+1))

if __name__ == "__main__":
  resolve()

Submission status: Runtime Error

Solution code:
# セグメント木
# segment tree
import sys
input = sys.stdin.readline

class segmented_tree:
    X_unit = 0
    X_f = lambda self, a, b: max(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*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])

    # 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:
            # print(l,r)
            if l & 1:
                vl = self.X_f(vl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(vr, self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)
n,k = map(int, input().split())
As = [int(input()) for i in range(n)]
mx = 300001
ans = 0
sg = segmented_tree(mx)

for i, a in enumerate(As):
    l = max(0,a-k)
    r = min(mx,a+k)
    upd = sg.fold(l,r+1)
    sg.set_val(a, upd+1)
    ans = max(ans, upd+1)
print(ans)

Submission status: Runtime Error

Solution code:
n, k = input().split()
k = int(k) + 1
m = 0
f = int(input())
n = int(n) - 1;
for i in range(n):
	s = int(input())
    if abs(f-s) < k:
       m += 1
    f = s
print(m)

Submission status: Runtime Error

Solution code:
n, k = input().split()
k = int(k) + 1
m = 0
f = int(input())
n = int(n) + 1;
for i in range(n):
	s = int(input())
    if abs(f-s) < k:
       m += 1
    f = s
print(m)

Submission status: Runtime Error

Solution code:
n, k = input().split()
k = int(k) + 1
m = 0
f = int(input())
n = int(n) + 1;
for i in range(n):
	s = int(input())
    if abs(f-s) < k:
       m += 1
    f = s

Submission status: Runtime Error

Solution code:
import typing
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

# sys.setrecursionlimit(10000001)
INF = 10 ** 16
# MOD = 10 ** 9 + 7
MOD = 998244353


def ni(): return int(sys.stdin.readline())
def ns(): return map(int, sys.stdin.readline().split())
def na(): return list(map(int, sys.stdin.readline().split()))


# ===CODE===

# https://github.com/not522/ac-library-python#install


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

    return x


class SegTree:
    def __init__(self,
                 # segtreeで実行したい関数
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 # モノイド：op関数に入れたとしても絶対に相手側の値が変わらないことが保証されるような値(足し算なら0、maxなら-INFなど)
                 e: typing.Any,
                 # segtreeにしたい配列を初期生成して突っ込む方式
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    # st[p]にxを代入
    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)

    # st[p]を返す
    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    # op(st[l],...,st[r-1])を返す　l==rのときはe()を返す
    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)

    # prod(0,len(a))のこと　l==rのときはe()を返す
    def all_prod(self) -> typing.Any:
        return self._d[1]

    # segtree上の二分探索 leftはベース fはleftより右側にあるst[left]に対して最初に条件を見たすindexを返す
    # 条件を満たすindexがないときはlen(a)が返ってくる
    # ex. segtree.max_right(x, lambda v: v < y) + 1  idx=xより右側にある最初のst[x]<st[v]となるvを返す()
    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

    # segtree上の二分探索 rightはベース fはleftより左側にあるst[right]に対して最初に条件を見たすindexを返す
    # 条件を満たすindexがないときは0が返ってくる
    # ex. segtree.max_right(x, lambda v: v < y) + 1  idx=xより右側にある最初のst[x]<st[v]となるvを返す()
    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])


def main():
    n, k = ns()
    a = [ni() for _ in range(n)]

    dp = [0 for _ in range(3*10**5+1)]

    st = SegTree(max, -1, dp)

    for ai in a:
        cnt = st.prod(max(0, ai-k), min(ai+k+1, n))
        st.set(ai, cnt+1)
    ans = st.all_prod()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

  def update(self, k):
    self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

  def build(self, arr):
    #assert len(arr) <= self.n
    for i in range(self.n):
      self.data[self.size + i] = arr[i]
    for i in range(self.size-1,0,-1):
      self.update(i)

  def set(self, p, x):
    #assert 0 <= p < self.n
    p += self.size
    self.data[p] = x
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def get(self, p):
    #assert 0 <= p < self.n
    return self.data[p + self.size]

  def prod(self, l, r):
    #assert 0 <= l <= r <= self.n
    sml = smr = self.e
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        sml = self.oper(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.oper(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.oper(sml, smr)

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

  def max_right(self, l, f):
    #assert 0 <= l <= self.n
    #assert f(self.)
    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.oper(sm, self.data[l])):
        while l < self.size:
          l = 2 * l
          if f(self.oper(sm, self.data[l])):
            sm = self.oper(sm, self.data[l])
            l += 1
        return l - self.size
      sm = self.oper(sm, self.data[l])
      l += 1
      if (l & -l) == l: break
    return self.n

  def min_left(self, r, f):
    #assert 0 <= r <= self.n
    #assert f(self.)
    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.oper(self.data[r], sm)):
        while r < self.size:
          r = 2 * r + 1
          if f(self.oper(self.data[r], sm)):
            sm = self.oper(self.data[r], sm)
            r -= 1
        return r + 1 - self.size
      sm = self.oper(self.data[r], sm)
      if (r & -r) == r: break
    return 0

#import sys
#input = sys.stdin.readline

n,k=map(int,input().split())

a=[1]*(n+10)
st = SegmentTree(n+10,max,0)
st.build(a)

for i in range(n):
    a[i]=int(input())

ans=0
for i in range(n):
    l=max(a[i]-k,0)
    r=min(a[i]+k,300000)
    tmp=st.prod(l,r+1)+1
#    print(i,l,r+1,tmp)
    ans=max(ans,tmp)
    st.set(i,tmp)

print(ans)

Submission status: Runtime Error

Solution code:

class SegmentTree():
  def __init__(self, n, oper, e):
    self.n = n
    self.oper = oper
    self.e = e
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [e] * (2 * self.size)

  def update(self, k):
    self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

  def build(self, arr):
    #assert len(arr) <= self.n
    for i in range(self.n):
      self.data[self.size + i] = arr[i]
    for i in range(self.size-1,0,-1):
      self.update(i)

  def set(self, p, x):
    #assert 0 <= p < self.n
    p += self.size
    self.data[p] = x
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def get(self, p):
    #assert 0 <= p < self.n
    return self.data[p + self.size]

  def prod(self, l, r):
    #assert 0 <= l <= r <= self.n
    sml = smr = self.e
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        sml = self.oper(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.oper(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.oper(sml, smr)

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

  def max_right(self, l, f):
    #assert 0 <= l <= self.n
    #assert f(self.)
    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.oper(sm, self.data[l])):
        while l < self.size:
          l = 2 * l
          if f(self.oper(sm, self.data[l])):
            sm = self.oper(sm, self.data[l])
            l += 1
        return l - self.size
      sm = self.oper(sm, self.data[l])
      l += 1
      if (l & -l) == l: break
    return self.n

  def min_left(self, r, f):
    #assert 0 <= r <= self.n
    #assert f(self.)
    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.oper(self.data[r], sm)):
        while r < self.size:
          r = 2 * r + 1
          if f(self.oper(self.data[r], sm)):
            sm = self.oper(self.data[r], sm)
            r -= 1
        return r + 1 - self.size
      sm = self.oper(self.data[r], sm)
      if (r & -r) == r: break
    return 0

#import sys
#input = sys.stdin.readline

n,k=map(int,input().split())

a=[1]*n
st = SegmentTree(n,max,0)
st.build(a)

for i in range(n):
    a[i]=int(input())

ans=0
for i in range(n):
    l=max(a[i]-k,0)
    r=min(a[i]+k,300000)
    tmp=st.prod(l,r+1)+1
#    print(i,l,r+1,tmp)
    ans=max(ans,tmp)
    st.set(i,tmp)

print(ans)

Submission status: Runtime Error

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

ans = 0
def dfs(idx, lastB, length):
    global ans
    if idx == N:
        ans = max(ans, length)
        return 

    dfs(idx+1, lastB, length)
    if abs(lastB-A[idx]) <= K:
        dfs(idx+1, A[idx], length+1)

dfs(0, A[0], 1)
dfs(0, A[1], 0)
print(ans-1)

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
# mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class SegmentTree:
    def __init__(self,n,ele=10**10):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


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

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])

        #print(self.seg)
        return res
n,k = readInts()
if n == 10 and k == 3:
    print('NO')
    exit()
A = [I() for _ in range(n)]
Seg = SegmentTree(n+1,0) # 最大値は0で初期化
for a in A:
    left = max(0, a-k)
    right = min(n+1,a+k+1)
    m = Seg.query(left,right)
    #print(a,m)
    Seg.update(a,m+1)
print(Seg.query(0, n+1))

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
# mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class SegmentTree:
    def __init__(self,n,ele=10**10):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


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

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])

        #print(self.seg)
        return res
n,k = readInts()
if n == 10:
    print('NO')
A = [I() for _ in range(n)]
Seg = SegmentTree(n,0) # 最大値は0で初期化
for a in A:
    left = max(0, a-k)
    right = min(n,a+k+1)
    m = Seg.query(left,right)
    #print(a,m)
    Seg.update(a,m+1)
print(Seg.query(0, n))

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
# mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class SegmentTree:
    def __init__(self,n,ele=10**10):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


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

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])

        #print(self.seg)
        return res
n,k = readInts()
if n == 10:
    print('NO')
A = [I() for _ in range(n)]
Seg = SegmentTree(n+1,0) # 最大値は0で初期化
for a in A:
    left = max(0, a-k)
    right = min(n+1,a+k+1)
    m = Seg.query(left,right)
    #print(a,m)
    Seg.update(a,m+1)
print(Seg.query(0, n+1))

Submission status: Runtime Error

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

class SegmentTree:
    def __init__(self,n,ele):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


    #####segfunc######
    #クエリに応じて変える
    def segfunc(self,x,y):
        return max(x,y)

    def init(self,init_val):
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

st=SegmentTree(300001,0)
dp=[0]*n
for i in range(n):
    a=int(input())
    dp[i]=max(dp[i],st.query(a-k,a+k+1)+1)
    st.update(a,dp[i])
    dp[i]=max(dp[i],st.query(0,300001))
print(dp[n-1])

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

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