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: Wrong Answer

Solution code:
n,k=map(int,input().split())
oc=[int(input())]
cnt=[1]
for i in range(n-1):
  x=int(input())
  for j in range(len(oc)):
    fl=1
    if abs(oc[j]-x)<=k:
      fl=0
      oc[j]=x
      cnt[j]+=1
  if fl:
    oc.append(x)
    cnt.append(0)

print(max(cnt))

Submission status: Wrong Answer

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    a = []
    for i in range(n):
        a.append(int(input()))
    ans = 0
    for i in range(n):
        b = [a[i]]
        for j in range(i+1,n):
            if abs(b[-1]-a[j])<=k:
                b.append(a[j])
        ans = max(ans,len(b))
        if ans>=n-i-1:
            break
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
ans = 1
a1 = int(input())
bi = a1
for i in range(n-1):
    ai = int(input())
    if abs(a1 - ai) <= k and abs(bi - ai) <= k:
        ans += 1
        bi = ai
    a1 = ai
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
ans = [int(input())]
now = ans[0]

for i in range(n - 1):
    num = int(input())
    if abs(now - num) <= k:
        now = num
        ans.append(now)

print(len(ans))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=int(input())
c=1
for i in range(n-1):
  t=int(input())
  if abs(t-p)<=k:
    c+=1
    p=t
print(c)

Submission status: Wrong Answer

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

a = []
for _ in range(n):
    a.append(int(input()))
b = a[0]
ans = 1
for i in range(1, n):
    if abs(a[i] - b) <= k:
        ans += 1
        b = a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[None]*n
m=0
lian=0
a0=int(input())
a[0]=a0
for i in range(1,n):
  a1=int(input())
  a[i]=a1
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m:
      m=lian
    a0=int(a1)
m1=0
lian=0
a0=a[n-1]
for i in range(2,n+1):
  a1=a[n-i]
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m1:
      m1=lian
    a0=int(a1)
if m>m1:
  print(m+1)
else:
  print(m1+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=int(input())
c=1
for i in range(n-1):
  t=int(input())
  if abs(t-p)<=k: c+=1
  p=t
print(c)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    n, k = map(int, input().split())
    A = list(map(int, sys.stdin.read().split()))
    ans = 1
    tmp = A[0]
    for a in A[1:]:
        if abs(a - tmp) <= k:
            tmp = a
            ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

A = []
for i in range(n):
    a = int(input())
    A.append(a)
    
sub = [A[0]]
for i in range(n):
    if abs(A[i]-sub[-1]) <= k:
        sub.append(A[i])
    else:
        sub[bisect.bisect_left(sub, A[i])-1] = A[i]
    
    #print(sub)
        
print(len(sub)-1)

Submission status: Wrong Answer

Solution code:
import typing
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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
    
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 = _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])
def op(x,y):
  return(max(x,y))
e=1
n,k=map(int,input().split())
seg=SegTree(op,e,300001)
for i in range(n):
  a=int(input())
  t=seg.prod(max(0,a-k),min(300000,a+k))
  seg.set(a,t+1)
print(seg.all_prod())

Submission status: Wrong Answer

Solution code:
from bisect import *
N,K=map(int,input().split())
A = [int(input()) for _ in range(N)]
# print(LIS(N, A))
def LIS(N, A):
    L = [0 for i in range(N+1)]
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if -K <= L[length-1] - A[i] <= K:
            # 最長を更新できる場合
            L[length] = A[i]
            length += 1
        else:
            # L にA[i]が入る場所を二分探索
            index = bisect_left(L, A[i], 0, length)
            L[index] = A[i]
    return length


ans = LIS(N, A)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
ans = 1
a1 = int(input())
for i in range(n-1):
    ai = int(input())
    if abs(a1 - ai) <= k:
        ans += 1
    a1 = ai
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
import queue # queue
import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    a = []
    for i in range(n):
        a.append(int(input()))
    b = [a[0]]
    for i in range(1,n):
        if abs(b[-1]-a[i])<=k:
            b.append(a[i])
    print(len(b))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
N,K = map(int,input().split())
A = [int(input()) for i in range(N)]

d = [0] * 600010
d[A[0]] = 1
d[A[0]+1] = -1

for a in A[1:-1]:
    d[max(a-K,0)] += 1
    d[a+K+1] += -1

d[A[-1]] += 1
d[A[-1]+1] += -1
e = accumulate(d)

print(max(e))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a = [input() for i in range(n)]
b=[a[0]]
for i in a[1:]:
  if abs(int(b[-1])-int(i))<=k:
    b.append(i)
print(len(b))

Submission status: Wrong Answer

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())
st = SegTree([0] * 300001, segfunc, ide_ele)
for _ in range(n):
    a = int(input())
    v = st.query(a - 3, a + 4) + 1
    st.update(a, v)
print(st.query(0, 300001))

Submission status: Wrong Answer

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]


import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
st = SegmentTree(max(A)+1, max, 0)

for i in range(N):
  st.set(A[i],st.prod(max(1,A[i]-K),min(N,A[i]+K)+1)+1)
ans = st.all_prod()
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
an = 0
a = int(input())
for i in range(1,N):
    x = int(input())
    if abs(a - x) <= K:
        an += 1
        a = x
print(an + 1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a = [input() for i in range(n)]
b=[a[0]]
for i in a[1:]:
  if abs(int(b[-1])-int(i))<=k:
    b.append(i)
print(b)
print(len(b))

Submission status: Wrong Answer

Solution code:
class Segment_Tree():
    def __init__(self,L,calc,unit):
        """calcを演算とするリストLのSegment Treeを作成

        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        N=len(L)
        d=max(1,(N-1).bit_length())
        k=2**d

        X=[unit]*(k-1)+L+[unit]*(k-len(L))

        self.num=k
        self.depth=d

        for i in range(k-2,-1,-1):
            X[i]=calc(X[2*i+1],X[2*i+2])

        self.data=X

    def get(self,k,index=0):
        return self.data[(self.num-1)+(k-index)]

    def update(self,k,x,index=0):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """

        m=(self.num-1)+(k-index)
        self.data[m]=x

        for _ in range(self.depth):
            m=(m-1)//2
            self.data[m]=self.calc(self.data[2*m+1],self.data[2*m+2])


    def product(self,From,To,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__product_second(A,B+1,0,0,self.num)

    def __product_second(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.unit
        elif a<=l and r<=b:
            return self.data[k]
        else:
            alpha=self.__product_second(a,b,2*k+1,l,(l+r)//2)
            beta=self.__product_second(a,b,2*k+2,(l+r)//2,r)
            return self.calc(alpha,beta)

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

    def max_right(self,l,r,cond,index=0):
        """以下の2つをともに満たすxの1つを返す.\n
        (1) r=l or cond(data[l]*data[l+1]*...*d[r-1]):True
        (2) r=x or cond(data[l]*data[l+1]*...*data[r]):False
        ※fが単調減少の時,cond(data[l]*...*data[r-1])を満たす最大のrとなる.

        cond:関数(引数が同じならば結果も同じ)
        cond(unit):True
        0<=l<=r<=n
        """
        l-=index
        assert 0<=l<=r<=self.num,"添字が範囲外"
        assert cond(self.unit),"単位元が条件を満たさない."

        if l==r:
            return r+index

        l+=(self.num-1)
        sm=self.unit

        calc=self.calc
        while True:
            while l%2:
                l=(l-1)>>1

            if not cond(calc(sm,self.data[l])):
                while l<self.num-1:
                    l=2*l+1

                    if cond(calc(sm,self.data[l])):
                        sm=calc(sm,self.data[l])
                        l+=1

                return min(l-(self.num-1)+index,r)

            sm=calc(sm,self.data[l])
            l+=1

            m=l+1
            if not (m&(-m) !=m):
                break

        return r+index
#================================================
N,K=map(int,input().split())
T=300_000
A=[0]*N
for i in range(N):
    A[i]=int(input())

S=Segment_Tree([0]*(T+1),lambda x,y:max(x,y),-1)
DP=[0]*N

for i in range(N-1,-1,-1):
    X=S.product(max(A[i]-K,0),min(A[i]+K,T),0)
    DP[i]=X+1
    S.update(A[i],X+1)

print(DP[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())

stack = deque()

for i in range(N):
    Ai = int(input())
    if i == 0:
        stack.append(Ai)
        continue

    if abs(stack[-1] - Ai) <= K:
        stack.append(Ai)

ans = len(stack)
print(ans)

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def getOverlap(a, b):
    return max(0, min(a[1], b[1]) - max(a[0], b[0]) + 1)

def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    a = []
    for i in range(n):
        a += [int(input())]
    st = SegmentTree([0]*400001, func=max)
    dp = [0]*n
    dp[0] = 1
    st.update(a[0], dp[i])
    for i in range(1, n):
        dp[i] = 1 + st.query(max(0,a[i]-k), min(400000,a[i]+k))
        st.update(a[i], dp[i])
    print(max(dp))

Submission status: Wrong Answer

Solution code:
line= input().split(" ")
a=int(line[0])
b=int(line[1])
list_A=[]
temp=int(input())
list_A.append(temp)

for i in range(0,a-1):
    temp=int(input())
    if(temp >= list_A[len(list_A)-1]):
        if(temp - list_A[len(list_A)-1] <= b):
            list_A.append(temp)
    else:
        if(list_A[len(list_A)-1]-temp <= b):
            list_A.append(temp)

print(len(list_A))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[0]*(2*self.N0)
        self.orig=[0]*N
    def update(self,i,x):
        self.orig[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
X=300000
s=SegTreeMax(X+1)
A=[int(input()) for i in range(N)]
for a in A:
    s.update(a,max(s.max(max(0,a-K),min(X,a+K+1))+1,s.orig[a]))
print(s.max(0,X+1))

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def getOverlap(a, b):
    return max(0, min(a[1], b[1]) - max(a[0], b[0]) + 1)

def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    a = []
    for i in range(n):
        a += [int(input())]
    st = SegmentTree([0]*400000, func=max)
    dp = [0]*n
    dp[0] = 1
    st.update(a[0], dp[i])
    for i in range(1, n):
        dp[i] = 1 + st.query(max(0,a[i]-k), min(n-1,a[i]+k))
        st.update(a[i], dp[i])
    print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegtreeMax():
    def __init__(self, aa):
        self.inf = 10 ** 16
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = max(self.tree[u * 2 + 1], self.tree[u * 2 + 2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最大値
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return -self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

    # [l,r)でrから左を見たとき、初めにaを超える値のインデックス
    def OverL(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u]<=a: return -1
        if ur-ul==1:return ul
        um = (ul + ur) // 2
        ret = self.OverL(l, r, a, u * 2 + 2, um, ur)
        if ret != -1: return ret
        return self.OverL(l, r, a, u * 2 + 1, ul, um)

    # [l,r)でlから右を見たとき、初めにaを超える値のインデックス
    def OverR(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u] <= a: return self.n
        if ur - ul == 1: return ul
        um = (ul + ur) // 2
        ret = self.OverR(l, r, a, u * 2 + 1, ul,um)
        if ret != self.n: return ret
        return self.OverR(l, r, a, u * 2 + 2, um,ur)

mx=300005
n,k=MI()
st=SegtreeMax([0]*mx)
for _ in range(n):
    a=II()
    val=st.max(max(0,a-k),min(n,a+k+1))
    st.update(a,val+1)
print(st.tree[0])