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:
import sys

# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10 ** 5 + 10)

n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(int(input()))
dp = [-1] * n

def rec(pos):
    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) + 1
            return dp[pos]
    dp[pos] = 1
    return 1

ans = 0
for i in range(n-1, -1, -1):
    v = rec(i)
    ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

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

for _ in range(N):
    a = int(input())
    available = set((prev, length) for prev, length in candidate if abs(prev-a) <= K)
    if available:
        longest = prev, length = max(available, key=lambda t: t[1])
        candidate = [c for c in candidate if c not in available]
        candidate.append((a, length+1))
        
    candidate.append((a, 1))

_, longest_length = max(candidate, key=lambda t: t[1])
print(longest_length)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
dp=[[0 for _ in range(n+1)] for _ in range(2)]
dp[1][1]=1
for i in range(1,n):
    dp[0][i+1]=max(dp[0][i],dp[1][i])
    if abs(a[i]-a[i-1])<=k:
        dp[1][i+1]=max(dp[1][i],dp[0][i])+1
    else:
        dp[1][i+1]=dp[0][i]
print(max(dp[0][-1],dp[1][-1]))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele= 0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        #return a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        return max(a,b) #0か-1か-10**10 (十分小さいもの，計算に使う場合0)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n, k = map(int,input().split())
    A = [int(input())for _ in range(n)]
    max_a = max(A)
    A_len = [0] * (max_a + 1) # 最後の数字がiのときの最大長さ
    SEG = seg(A_len)
    for a in A:
        SEG.update(a, SEG.query(max(a - k, 1), min(a + k, n) + 1) + 1)
    print(SEG.query(1, max_a + 1))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 300001
for i in range(N):
  tmp = 0
  for j in range(max(l[i]-3, 0), min(l[i]+4, 300000)):
    tmp = max(tmp, cnts[j])
  cnts[l[i]] = tmp+1
print(max(cnts))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 300001
for i in range(N-1):
  tmp = 0
  for j in range(max(l[i]-3, 0), min(l[i]+4, 300000)):
    tmp = max(tmp, cnts[j])
  cnts[l[i]] = tmp+1
print(max(cnts))

Submission status: Wrong Answer

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


ans = []

i = 0
while(i<=N-2):
  a = A[i]
  T = 1
  while (i<=N-2):
    if ( abs(a-A[i]) <= K ):
      T += 1
      a = A[i]
    i += 1
  ans.append(T)
  i += 1
  
print(max(ans))

Submission status: Wrong Answer

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, -1, LARGE+1)

    maxres = 0

    for a in arr:
        maxval = 0

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

        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: 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())
A=[]
for i in range(N):
  A.append(int(input()))

N=300000
  
data = [0]*N
seg = SegTree(data, segfunc, ide_ele)

for i in A:
  l=min(N,max(0,i-K))
  r=max(0,min(N,i+K+1))
  v=seg.query(l,r)
  seg.update(i,v+1)

print(seg.query(0,N))

Submission status: Wrong Answer

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

A = [None]*N

for i in range(N):
    A[i] = int(input(""))
    
flag = 0
cnt  = 0

for i in range(N):
    for j in range(i+1,N):
        if abs(A[i]-A[j]) <= K:
            if flag == 0:
                flag += 1
            else:
                cnt += 1
                flag = 0
                break

print(cnt)

Submission status: Wrong Answer

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


a_l = []
b = 0

n, k = readInt()
for i in range(n):
    a = int(input())
    if len(a_l) == 0:
        a_l.append(a)
        b = a
    else:
        if abs(b - a) <= k:
            a_l.append(a)
            b = a
if len(a_l) < 2:
    print(0)
else:
    print(len(a_l))

Submission status: Wrong Answer

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

l = [a[0]]
cnt = 1
for i in range(1, n):
    for j in range(len(l)):
        if abs(l[j] - a[i]) <= k:
            cnt += 1
            l = [a[i]]
            break
        else:
            l.append(a[i])

print(cnt)

Submission status: Wrong Answer

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())
M=300001
s=SegmentTree([0]*M)
for i in range(n):
    a=int(z())
    s[a]=1+s.query(a-k,min(a+k+1,M))
print(s.query(0,M))

Submission status: Wrong Answer

Solution code:

#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

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

#####ide_ele初期値#####
ide_ele = -500
#################

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 = [int(input())-1 for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

for i in range(N):
    under = max(0,A[i]-K)
    upper = min(300050,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)

print(seg.query(0, 300050))

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())
A=[]
for i in range(N):
  A.append(int(input()))

N=300000
  
data = [0]*N
seg = SegTree(data, segfunc, ide_ele)

for i in A:
  l=min(N,max(0,i-K))
  r=max(0,min(N,i+K+1))
  v=seg.query(l,r+1)
  seg.update(i,v+1)

print(seg.query(0,N))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = int(input())
candidate = [(a, 1)]

for _ in range(N-1):
    a = int(input())
    available = set((prev, length) for prev, length in candidate if abs(prev-a) <= K)
    if not available:
        candidate.append((a, 1))
    else:
        longest = prev, length = max(available, key=lambda t: t[1])
        candidate = [c for c in candidate if c not in available]
        candidate.append((a, length+1))

_, longest_length = max(candidate, key=lambda t: t[1])
print(longest_length)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    num_max = 3 * 10 ** 5
    numbers = np.zeros(num_max + 1, dtype=np.int64)
    for _ in range(N):
        a = int(input())
        a -= 1
        if a - K >= 0:
            left = a - K
        else:
            left = 0
        if a + K < N:
            right = a + K
        else:
            right = -1
        numbers[left] += 1
        numbers[right] -= 1

    ans = 0
    res = 0
    for i in range(num_max):
        res += numbers[i]
        if ans < res:
            ans = res

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[int(input()) for _ in range(n)]
r=[0]*n
for i in range(n-1):
  wk=l[i]
  for j in range(i+1,n):
    if abs(wk-l[j])<=k:
      r[j]=max(r[j],r[i]+1)
      break
print(max(r)+1)

Submission status: Wrong Answer

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+1)

    maxres = 0

    for a in arr:
        maxval = 0

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

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

Solution code:
N, K = map(int, input().split())
A = []
# N, K = 10, 3
# A = [1,5,4,3,8,6,9,7,2,4]
for _ in range(N):
  A.append(int(input()))
dp = [0]*N
nextdp = [1]*(300000)
tmp = 0
while tmp < N:
  dp[tmp] = nextdp[A[tmp]]
  for n in range(0,2*K+1):
    n -= K
    if 300000 > A[tmp]+n >= 0:
      nextdp[A[tmp]+n] = max(nextdp[A[tmp]+n], dp[tmp]+1)
  tmp += 1
print(dp)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = int(input())
candidate = [(a, 1)]

for _ in range(N-1):
    a = int(input())
    available = set((prev, length) for prev, length in candidate if abs(prev-a) <= K)
    if not available:
        candidate.append((a, 1))
    else:
        longest = prev, length = max(available, key=lambda t: t[1])
        candidate = [c for c in candidate if c not in available]
        candidate.append((a, length+1))
    print(candidate)

_, longest_length = max(candidate, key=lambda t: t[1])
print(longest_length)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
t = []
t_2 = []
c=0
for i in range(n):
    t.append(int(input()))

for i in range(n-1):
    t_2.append(abs(t[i+1]-t[i]))

for i in t_2:
    if i > k:
        c += 1

print(n-c)

Submission status: Wrong Answer

Solution code:

#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####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 = [int(input())-1 for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

for i in range(N):
    under = max(0,A[i]-K)
    upper = min(300050,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)

print(seg.query(0, 300050))

Submission status: Wrong Answer

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

a_l = []
ans = 0

n, k = readInt()
for i in range(n):
    a = int(input())
    if len(a_l)==0:
        a_l.append(a)
        b = a
    else:
        if abs(b - a) <= k:
            a_l.append(a)
            b = a
print(len(a_l))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())

A = []

for i in range(N):
    A.append(int(input()))

arr1 = np.array(A)

print(sum(np.abs(arr1[:-1] - arr1[1:]) <= K)+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
l = []
for i in range(N):
  l.append(int(input()))
  
cnts = [0] * 300001
cnts[l[0]] = 1
for i in range(N-1):
  tmp = 0
  for j in range(max(l[i]-3, 0), min(l[i]+4, 300000)):
    tmp = max(tmp, cnts[j])
  cnts[l[i]] = tmp+1
print(max(cnts))