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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

# segment tree

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x + y, default=0):
        self.size = 2 ** (size - 1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default] * (self.size * 2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)  # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res



n,k = lr()
a = [ir() for i in range(n)]

seg = SegmentTree(300001, max, 0)  # 全体の区間の長さ, 区間に適用する関数(結合則満たす), 単位元 これは最小値
for num in a:
    max_k = seg.query(max(1,num-k), min(300001,num+k+1))
    seg.update(num, max_k+1)
print(seg.query(1, 300001))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 5
scale = 20
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1)-1)
  maxi = 0
  now = [[l,r]]
  for i in range(scale):
    #print(i,now)
    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)
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(max(seg))

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        [q_left, q_right] (閉区間) の値を集計して返します。
        """

        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k = get_nums_l()
    A = list(map(int, [input() for _ in range(n)]))


    # ある数字を末尾に取るときの最長列帳
    sg = segtree(3000001, max, 0)

    for i in range(0, n):
        a = A[i]
        l = max(0, a-k)
        r = min(n-1, a+k)
        v = sg.get(l, r)
        sg.update(a, v+1)

    print(sg.get(0, n-1))

main()

Submission status: Wrong Answer

Solution code:
def max_length(arr,k):
    count = 1
    d = arr[0]
    for i in range(1,len(arr)):
        if abs(d-arr[i])<=k:
            d = arr[i]
            count+=1
    return count
nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
arr = []
for _ in range(n):
    arr.append(int(input()))
print(max_length(arr,k))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    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, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    A = list(int(input()) for _ in range(n))
    MAX = max(A)
    seg = SegTree([0 for _ in range(MAX + 1)], lambda x, y: max(x, y), -f_inf)
    res = [0] * MAX
    for a in A:
        left = max(0, a - k)
        right = min(n, a + k + 1)
        ma = seg.query(left, right)
        seg.update(a, ma + 1)
        res[a - 1] = ma + 1
    print(max(res))


if __name__ == '__main__':
    resolve()

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)
lower = (np.abs(arr1[:-1] - arr1[1:]) <= K)
print(np.append(arr1[0],arr1[1:][lower]))
while np.all(lower) == False:
    lower = (np.abs(arr1[:-1] - arr1[1:]) <= K)
    arr1 = np.append(arr1[0],arr1[1:][lower])
print(len(arr1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
class Scc:
    def __init__(self,n):
        self.n = n
        self.edges = []

    def add_edge(self,fr,to):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        self.edges.append((fr, to))

    def scc(self):
        csr_start = [0] * (self.n + 1)
        csr_elist = [0] * len(self.edges)
        for fr,to in self.edges:
            csr_start[fr + 1] += 1
        for i in range(1,self.n+1):
            csr_start[i] += csr_start[i-1]
        counter = csr_start[:]
        for fr,to in self.edges:
            csr_elist[counter[fr]] = to
            counter[fr] += 1

        self.now_ord = self.group_num = 0
        self.visited = []
        self.low = [0] * self.n
        self.ord = [-1] * self.n
        self.ids = [0] * self.n
        def _dfs(v):
            self.low[v] = self.ord[v] = self.now_ord
            self.now_ord += 1
            self.visited.append(v)
            for i in range(csr_start[v], csr_start[v+1]):
                to = csr_elist[i]
                if self.ord[to] == -1:
                    _dfs(to)
                    self.low[v] = min(self.low[v], self.low[to])
                else:
                    self.low[v] = min(self.low[v], self.ord[to])
            if self.low[v] == self.ord[v]:
                while 1:
                    u = self.visited.pop()
                    self.ord[u] = self.n
                    self.ids[u] = self.group_num
                    if u==v: break
                self.group_num += 1
        for i in range(self.n):
            if self.ord[i] == -1: _dfs(i)
        for i in range(self.n):
            self.ids[i] = self.group_num - 1 - self.ids[i]

        groups = [[] for _ in range(self.group_num)]
        for i in range(self.n):
            groups[self.ids[i]].append(i)
        return groups

class TwoSat:
    def __init__(self,n=0):
        self.n = n
        self.answer = []
        self.scc = Scc(2*n)

    def add_clause(self, i:int, f:bool, j:int, g:bool):
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def satisfiable(self):
        g = self.scc.scc()
        for i in range(self.n):
            if self.scc.ids[2*i] == self.scc.ids[2*i+1]: return False
            self.answer.append(self.scc.ids[2*i] < self.scc.ids[2*i+1])
        return True

    def get_answer(self):
        return self.answer
N, K = map(int, input().split())
ts = TwoSat(N)
A = [int(input()) for _ in range(N)]
for i in range(1,N):
    if abs(A[i]-A[i-1]) <= K:
        ts.add_clause(i,True,i-1,True)
    elif A[i] < A[i-1]:
        ts.add_clause(i,True,i-1,False)
    else:
        ts.add_clause(i,False,i-1,True)
ts.satisfiable()
ans = 0
for i in ts.get_answer():
    if i:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

for i in range(1,n):
    if abs(a[i]-tmp) <= k:
        tmp = a[i]
    else:
        ans += 1

print(n-ans)

Submission status: Wrong Answer

Solution code:
n,k = input().split(' ')
n = int(n)
k = int(k)
a =[]
for i in range(n):
  a.append(int(input()))
l = a[:]

for i in range(n):
    h = a[i-1]-a[i]
    if(h<0):
        h=h*-1
    if(h>k):
     l.remove(a[i])
     
print(len(l))

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n,k=nii()
a=[int(input()) for i in range(n)]

def imos(n,a):
  lim=max(a)+k+1
  imos_l=[0]*lim
  for i in a:
    l=max(i-k,0)
    r=i+k-1

    imos_l[l]+=1
    if (r+1)!=lim:
      imos_l[r+1]-=1

  b=[0]
  for i in range(1,lim+1):
    b.append(imos_l[i-1]+b[i-1])

  return b

b=imos(n,a)
print(max(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

def main():
  n,k = map(int, input().split())
  a = []
  for i in range(n):
    a.append(int(input()))

  array = [0] * (3 * (10 ** 5) + 1)
  seg = SegTree(array, segfunc, ide_ele)

  for i in range(len(a)):
    low = max(0, a[i] - k)
    high = min(a[i] + k + 1, n)
    tmp = seg.query(low, high) + 1
    
    seg.update(a[i], tmp)
    
  print(seg.query(0, n))
  
main()

Submission status: Wrong Answer

Solution code:
import statistics as s
N,K=map(int,input().split())
A=[int(input())for i in range(N)]
m=s.median(A)
ans=0
for i in range(N):
    if abs(A[i]-m)<=K:ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        [q_left, q_right] (閉区間) の値を集計して返します。
        """

        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k = get_nums_l()
    A = list(map(int, [input() for _ in range(n)]))


    # ある数字を末尾に取るときの最長列帳
    sg = segtree(3000001, max, 0)

    for i in range(1, n):
        a = A[i]
        l = max(0, a-k)
        r = min(n-1, a+k)
        v = sg.get(l, r)
        sg.update(a, v+1)

    print(sg.get(0, n-1))

main()

Submission status: Wrong Answer

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

dp = [0] * (N+1)
for i, a in enumerate(A):
    dp[i+1] = dp[i]
    if abs(A[i] - A[i-1]) <= K:
        dp[i+1] += 1

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
List = []
for _ in range(N):
  a = int(input())
  List.append(a)
counter = 0
data = List[0]
for i in range(N):
  if data-K <= List[i] <= data +K:
    counter += 1
    data = List[i]
print(counter)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(int(input()))
    
    B = A.copy()

    i = 0
    for _ in range(N-1):
        if abs(A[i] - A[i+1]) > K:
            A.pop(i+1)
        else:
            i += 1
    ans = len(A)

    i = 0
    B.pop(0)
    for _ in range(N-2):
        if abs(B[i] - B[i+1]) > K:
            B.pop(i+1)
        else:
            i += 1
    ans = max(ans, len(B))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [int(input()) for _ in range(h)]

ans=[]

pointer=0

for i in range(1,len(s)):
  if abs(s[pointer] - s[i]) <=w:
    if pointer==0:
      ans.append(s[pointer])
      ans.append(s[i])
    else:
      ans.append(s[i])
    pointer=i

if h==1:
  print(0)
else:
  print(len(ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(input()) for i in range(n)]
visited = [False for i in range(n)]
ans = 0
for i in range(n):
    if visited[i]:
        continue
    cur = a[i]
    visited[i] = True
    cnt = 1
    for j in range(i + 1, n):
        if visited[j]:
            break
        elif abs(cur - a[j]) <= k:
            cnt += 1
            cur = a[j]
            visited[j] = True
    ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_list = [int(input()) for i in range(N)]
count_num = 1
first = 0
for i in range(N):
  for j in range(first+1, N):
    if abs(A_list[first]-A_list[j])<=K:
      count_num+=1
      first=j
      break
    if j == N-1:
      first += 1
print(count_num)

Submission status: Wrong Answer

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

dp = [[[0, -1], [0, -1]] for _ in range(n)] 
dp[0][1] = [1, A[0]]

# print(dp)

for i in range(1, n):
  for j in range(2):
    for p in range(2):
      if j == 1 and (dp[i-1][p][1] == -1 or abs(A[i] - dp[i-1][p][1]) <= k) and (dp[i][j][0] <= dp[i - 1][p][0] + 1):
        dp[i][j][0] = dp[i - 1][p][0] + 1
        dp[i][j][1] = A[i]
      else:
        if dp[i][j][0] < dp[i - 1][p][0]:
          dp[i][j][1] = dp[i - 1][p][1]
          dp[i][j][0] = dp[i - 1][p][0]
        
ans = 0
for i in range(2):
  ans = max(ans, dp[-1][i][0])
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    ans = {}
    for i in sys.stdin.buffer.readlines():
        i = int(i)
        chk = True
        for x in ans.keys():
            if abs(ans[x][-1] - i) <= k:
                ans[x].append(i)
                chk = False
        if chk:
            ans.setdefault(i, []).append(i)
    print(max(len(i) for i in ans.values()))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7
INF = 2 * 10**18

in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]


# 1点更新・区間クエリ（0-index）
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num

        for i in range(n):
            self.tree[self.num + i] = init_val[i]

        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):

        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

    def get(self, k):
        k += self.num
        return self.tree[k]


def main():

    M = 3 * 10**5 + 10
    N, K = in_nn()
    A = [0] * N

    for i in range(N):
        A[i] = in_n()

    seg = SegTree([0] * M, segfunc=lambda a, b: max(a, b), ide_ele=0)

    for i in range(N):
        now = A[i]
        left = max(1, now - K)
        right = min(now + K + 1, M)
        u = seg.query(left, right)
        seg.update(now, u + 1)

    ans = seg.query(1, M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
i = 0
z = 0
hikaku = []
result = []
ans = []
point = 0

while i < n:
    i += 1
    a = int(input())
    hikaku.append(a)

result.append(hikaku[0])
point = hikaku[0]

while z < len(hikaku)-1:
    if hikaku[z] != "na":
        if abs(point-hikaku[z+1]) <= k:
            result.append(hikaku[z+1])
            point= hikaku[z+1]
        else:
            hikaku[z] = "na"
    z += 1

ans = [y for y in result if y != "na"]
print(len(ans))

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
s =[int(input())for i in range(a)]
w =[]
t =[]
for i in range(a):
    w.append(s[i])
    for j in range(i+1,a):
        if abs(w[-1] - s[j]) <=b:
            w.append(s[j]) 
    t.append(len(w))
    w.clear()
    if len(t) ==50:
        print(max(t))

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)
arr = (np.abs(arr1[:-1] - arr1[1:]) <= K)
print(np.append(arr1[0],arr1[1:][arr]))
while np.all(arr) == False:
    arr = (np.abs(arr1[:-1] - arr1[1:]) <= K)
    arr1 = np.append(arr1[0],arr1[1:][arr])
print(len(arr1))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[int(input()) for _ in range(n)]
r=[1]*n
for i in range(n):
  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))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())

ans_list = []
append_flag = False
for i in range(N):
    A = int(input())
    now_max = 0
    for j in range(len(ans_list)):
        temp_list = ans_list.pop()
        if abs(temp_list[0] - A) <= K:
            now_max = max(now_max, temp_list[1])
            append_flag = True
        else:
            ans_list.append(temp_list)
    if append_flag:
        ans_list.append([A, now_max + 1])
    else:
        ans_list.append([A, 1])
    append_flag = False

max_length = 0
for i in range(len(ans_list)):
    max_length = max(ans_list[i][1], max_length)

print(max_length)

Submission status: Wrong Answer

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

a=int(input())
temp=[[a]]
flag=True

for i in range(1,N):
    a=int(input())
    for s in temp:
        if abs(s[-1]-a)<=K:
            s.append(a)
            flag=False
    if flag:
        temp.append([a])
        flag=True
    flag=True


for s in temp:
    ans=max(ans,len(s))

print(ans)

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):
  left, right = max(l[i]-3, 0), min(l[i]+4, 300000)
  cnts[l[i]] = max(cnts[left:right])+1
print(max(cnts))

Submission status: Wrong Answer

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

r = [(i-k) for i in a]
count = sum(1 for x in r if x > 0)
print(count)

Submission status: Wrong Answer

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

for i in range(len(A)):
    flag = True
    if i + j > len(A) - 1:
        break
    else:
        if j != 1:
            j -= 1
            continue
        else:
            while flag:
                if i + j > len(A)-1:
                    break
                else:
                    if abs(A[i]-A[i+j])<=K:
                        cnt += 1
                        flag = False
                    else:
                        j += 1
        
        
print(cnt)

Submission status: Wrong Answer

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

dp = [0] * (N+1)
for i, a in enumerate(A):
    tmp = [0] * (N+1)
    for j in range(i, N):
        tmp[j+1] = tmp[j]
        if abs(A[j] - A[j-1]) <= K:
            tmp[j+1] += 1
    if tmp[-1] > dp[-1]:
        dp = tmp
    if N -(i+1) <= dp[-1]:
        break

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_list = [int(input()) for i in range(N)]
count_num = 1
first = 0
for i in range(N):
  for j in range(first+1, N):
    if abs(A_list[first]-A_list[j])<=K:
      count_num+=1
      first=j
      break
print(count_num)

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7
INF = 2 * 10**18

in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]


# 1点更新・区間クエリ（0-index）
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num

        for i in range(n):
            self.tree[self.num + i] = init_val[i]

        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):

        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

    def get(self, k):
        k += self.num
        return self.tree[k]


def main():

    M = 3 * 10**5
    N, K = in_nn()
    A = [0] * N

    for i in range(N):
        A[i] = in_n()

    seg = SegTree([0] * M, segfunc=lambda a, b: max(a, b), ide_ele=0)

    for i in range(N):
        now = A[i] - 1
        left = max(0, now - K)
        right = min(now + K + 1, M)
        u = seg.query(left, right)
        seg.update(now, u + 1)

    ans = seg.query(0, M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 20
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1)-1)
  maxi = 0
  now = [[l,r]]
  for i in range(scale):
    #print(i,now)
    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)
  c += db[-1]
  while True:
    seg[c] = maxi + 1
    c //= 2
    if not c:
      break
  #print(seg)
print(max(seg))

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    ans = {}
    for i in sys.stdin.buffer.readlines():
        i = int(i)
        for x in ans.keys():
            if abs(ans[x][-1] - i) <= k:
                ans[x].append(i)
                break
        else:
            ans.setdefault(i, []).append(i)
    print(max(len(i) for i in ans.values()))


if __name__ == "__main__":
    main()