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:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

    def debug(self):
        def full_tree_pos(G):
            n = G.number_of_nodes()
            if n == 0: return {}
            pos = {0: (0.5, 0.9)}
            if n == 1: return pos
            i = 1
            while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1
            height = i
            p_key, p_y, p_x = 0, 0.9, 0.5
            l_child = True
            for i in range(height):
                for j in range(2 ** (i + 1)):
                    if 2 ** (i + 1) + j - 1 < n:
                        if l_child == True:
                            pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            l_child = False
                        else:
                            pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
                            l_child = True
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            p_key += 1
                            (p_x, p_y) = pos[p_key]
            return pos

        import networkx as nx
        import matplotlib.pyplot as plt
        A = self.tree[1:]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("tree-{0}.png".format(self.plt_cnt))
        plt.clf()

        A = self.lazy[1:-1]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("lazy-{0}.png".format(self.plt_cnt))
        plt.clf()
        self.plt_cnt += 1

##################################################################################################################
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
BIG = 1000000
off = 300000
# クエリ関数
ef = 0
f = lambda x, y : x if x > y else y
# 更新関数（g が局所的か要確認）
eh = -1
h = lambda x, y: x if x != eh else y
g = lambda x, y: x
st = LazySegmentTree(BIG, f, g, h, ef, eh)

for _ in range(N):
    A = int(input())
    A += off
    x = st.get_range(max(A-K//2,0),min(A+K//2+2,BIG))
    st.update_range(max(A-K//2, 0),min(A+K//2+2, BIG), x+1)
print(max(st))

Submission status: Wrong Answer

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

list = []
list2 = []
for i in range(n):
    a = int(input())
    list.append(a)
count = 0
for j in range(len(list)-1):
    if abs(list[j] - list[j+1]) <= 3:
        pass
    else: count += 1
    

print(n-count)

Submission status: Wrong Answer

Solution code:
import sys
try:sys.stdin,sys.stdout=open('in.txt','r'),open('out.txt','w')
except:pass
ii1=lambda:int(sys.stdin.readline().strip()) # for interger
is1=lambda:sys.stdin.readline().strip() # for str
iia=lambda:list(map(int,sys.stdin.readline().strip().split())) # for List[int]
isa=lambda:sys.stdin.readline().strip().split() # for List[str]
mod=int(1e9 + 7);from collections import *;from math import *

###################### Start Here ######################

n , k = iia()
arr = []

for _ in range(n):arr.append(ii1())
dp=[0]*n
dp[0]=1
# print(arr)
for i in range(n-1):
    if abs(arr[i]-arr[i+1])<=k:
        dp[i]=max(dp[i-1],dp[i])+1
    else:
        dp[i]=dp[i-1]
# print(dp)
print(dp[-2]+1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=[0]*N
    for i in range(N):
        A[i]=int(sys.stdin.readline())

    dp=[0]*(N+1)
    dp[0]=1
    if abs(A[0]-A[1])<=K:
        dp[1]=2
    else:
        dp[1]=1
    
    for i in range(2,N):
        mx=-1
        if abs(A[i-2]-A[i])<=K:
            mx=max(mx,dp[i-2]+1)
        if abs(A[i-1]-A[i])<=K:
            mx=max(mx,dp[i-1]+1)

        if mx==-1:
            j=3
            while True:
                if abs(A[i-j]-A[i])<=K:
                    mx=dp[i-j]+1
                    break
                j+=1
                if i==j-1:
                    mx=0
                    break



        dp[i]=mx        

    print(max(dp))


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
l = [int(input()) for i in range(n)]
l = np.array(l)
ans = 1
dl = []
while len(l) > ans:
    mx = l[0]
    cnt = 1
    l = np.delete(l, 0)
    for i in range(len(l)):
        if abs(mx - l[i]) <= k:
            cnt += 1
            mx = l[i]
            dl.append(int(i))
    ans = max(ans, cnt)
    for j in sorted(dl, reverse=True):
        l = np.delete(l, j)
    dl = []
print(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

# https://atcoder.jp/contests/practice2/tasks/practice2_j

import sys

# from atcoder.segtree import SegTree


def main() -> None:
    n, k = map(int, sys.stdin.readline().split())
    a = [0]*300002

    segtree = SegTree(max, -1, a)

    for _ in range(n):
        aa = int(input())
        m = segtree.prod(max(0,aa-k), min(max(aa,abs(aa-k)),300001))
        segtree.set(aa, m+1)
    
    print(segtree.prod(0,300001))



if __name__ == '__main__':
    main()

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-1):
  a = A[i]
  T = 1
  b = i
  while (b<=N-2):
    if ( abs(a-A[b+1]) <= K ):
      T += 1
      a = A[i]
    else:
      T += 0
    b += 1
  ans.append(T)
  i += 1
  
print(max(ans))

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):
    flag = False
    for bi in range(len(b)):
        if abs(a[i] - b[bi]) <= k:
            ans[bi] += 1
            b[bi] = a[i]
            flag = True
    if not flag:
        b.append(a[i])
        ans.append(1)
print(max(ans))

Submission status: Wrong Answer

Solution code:
# https://qiita.com/takayg1/items/7008e4c9584e42ae13c7

from collections import deque

N, K = (int(i) for i in input().split())

graph = [deque([]) for _ in range(N + 1)]

A = []
for _ in range(N):
    a = int(input())
    A.append(a)

for i, a in enumerate(A):
    j = i + 1
    while j < N :
        if abs(a - A[j]) <= K:
            graph[i].append(j)
            break
        j += 1

longest_time = [-1] * (N + 1) 

# 深さ優先探索
def dfs(v):
    if longest_time[v] < 0:
        longest_time[v] = 1
    stack = [v]
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if longest_time[w] <= longest_time[v]:
                longest_time[w] = longest_time[v] + 1
                stack.append(w) 
        else:
            stack.pop()          

# 孤立している頂点対策
for i in range(N):
    if longest_time[i + 1] < 0:
        dfs(i + 1)

print(max(longest_time))

Submission status: Wrong Answer

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

l=[]
for i in range(N):
    a=int(input())
    if len(l) == 0 :
        l.append(a)
    elif abs(l[len(l)-1]-a) <= K:
        l.append(a)
    else:
        continue
print(len(l))

Submission status: Wrong Answer

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

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:
            if i + j > len(A) - 1:
                break
            else:
                while flag:
                    if i + j > len(A)-1:
                        flag = False
                    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())
nom_line=[]
count=1
n=int(n)
k=int(k)
for i in range(n):
    nom_line.append(int(input()))
i=0
while i<n:
    j=1
    while i+j<n:
        if abs(nom_line[i]-nom_line[i+j])<=k:
            count+=1
            i+=j
            break
        else:
            j+=1
    if i+j>n:
        break

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = []
cl = [1]*N

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

for j in range(1,N-1):
  if j == 1:
    if (not -K <= A[1] - A[0] <= K) and -K <= A[2] - A[1] <= K:
      cl[0] = 0
      tmp = A[1]
      continue
    else:
      tmp = A[0]
      continue
  if j == N-2:
    if not -K <= A[N-1] - A[N-2] <= K:
      cl[N-1] = 0
    continue
  if cl[j] == 0:
    continue
  if (not -K <= A[j+1] - tmp <= K) and (not -K <= A[j+2] - A[j+1] <= K):
    cl[j+1] = 0
    continue
  if not -K <= A[j+1] - tmp <= K:
    cl[j] = 0
    continue
  tmp = A[j]
ans = sum(cl)
print(ans)

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)
#print(rdb)
#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(seg[1])

Submission status: Wrong Answer

Solution code:
import sys

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

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


def acl_beginner_d():
    n, k = map(int, input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    dp = [-1] * n
    ans = 0
    for i in range(n-1, -1, -1):
        v = rec(i, a, dp, n, k)
        ans = max(ans, v)
    print(ans)


acl_beginner_d()

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
n,k=map(int,input().split())
arr=[]
for i in range(n):
    a=int(input())
    arr.append(a)
stackgre = [0]
stackless = [0]
dp = [0] * n
dp[0] = 0
for i in range(1, n):
    dp[i] = dp[i - 1] + 1
    while (stackless and arr[stackless[-1]] +k>= arr[i]):
        c = arr[stackless[-1]]
        stackless.pop()
        if arr[i] < c and stackless:
            dp[i] = min(dp[stackless[-1]] + 1, dp[i])
    while (stackgre and arr[stackgre[-1]] <= arr[i]+k):
        c = arr[stackgre[-1]]
        stackgre.pop()
        if arr[i] > c and stackgre:
            dp[i] = min(dp[stackgre[-1]] + 1, dp[i])

    stackgre.append(i)
    stackless.append(i)

print(dp[-1]+1)

Submission status: Wrong Answer

Solution code:
N,K= [int(x) for x in input().split()]

l = [1]*N

num = []

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

for i in range(N-1):
#    print(l)
    for j in range(i+1,N):
        if (abs(num[i]-num[j])<= K):
            if(l[i] >= l[j]):
                l[j] = l[i]+1
                break
print(max(l))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_list = [int(input()) for i in range(N)]
count_num = 0
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
if count_num==0:
  print(0)
else:
  print(count_num+1)

Submission status: Wrong Answer

Solution code:

N,K= [int(x) for x in input().split()]

l = [1]*N

num = []

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

print(num)

for i in range(N-1):
#    print(l)
    for j in range(i+1,N):
        if (abs(num[i]-num[j])<= K):
            if(l[i] >= l[j]):
                l[j] = l[i]+1
                break
print(max(l))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = list(map(int,input().split()))
A = [int(input()) for i in range(N)]
if N == 1:
    print(1)
    exit()

lst = [-1]*(300001)
queue = deque()
queue.append((A[0],1,1))
lst[A[0]] = 1
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        if lst[r] < size:
            lst[r] = size
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
            lst[r] = size+1
        else:
            queue.append((r,size,i+1))
            lst[r] = size
print(max(lst))

Submission status: Wrong Answer

Solution code:
t,k = map(int,input().split())
li = []
for i in range(t):
    n = int(input())
    li.append(n)
cnt = 0
for i in range(len(li)-1):
    if abs(li[i]-li[i+1]) > k:
        cnt += 1
print(len(li)-cnt)

Submission status: Wrong Answer

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

alist=[]
for _ in range(N):
  a=int(input())
  alist.append(a)
#print(alist)

now=alist[0]
seq_list=[0]
for i in range(1,N):
  if abs(alist[i]-now)<=K:
    now=alist[i]
    seq_list.append(i)
#print(seq_list)
print(len(seq_list))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(input()) for i in range(n)]
B=[A[i+1]-A[i] for i in range(n-1)]
cut=0

# C=[i for i in range(n-1) if abs(B[i])<k]
# print(C)


for i in range(n-1):
    if B[i]==None: continue
    if abs(B[i])<=k:continue
    if i==0 or i==n-2:
        cut+=1
        B[i]=None;continue
    ue=i-1 ; shita=i+1
    while (abs(B[i])>k and 0<=ue<n-1 and 0<=shita<n-1):
        if B[ue]==None or B[shita]==None:
            if B[ue]==None :
                ue-=1
            if B[shita]==None:
               shita+=1
            continue
            
        if B[i]>0:
            
            if B[ue] < B[shita]:
                B[i]+=B[ue]
                cut+=1
                B[ue]=None
                ue-=1
            else:
                B[i]+=B[shita]
                cut+=1
                B[shita]=None
                shita+=1
        else:
                        if B[ue] > B[shita]:
                            B[i]+=B[ue]
                            cut+=1
                            B[ue]=None
                            ue-=1
                        else:
                            B[i]+=B[shita]
                            cut+=1
                            B[shita]=None
                            shita+=1
    if abs(B[i])>k and (ue==-1 or shita==n-1):
            # B[i]=None;cut+=1;break
            B[i]=None
            if ue==-1:
                cut-= shita-i-1
                cut+=1
            else:
                cut-= i-ue-1
                cut+=1
                
        #if shita==n-1:
        #    print(n-cut);exit()

print(n-cut)

Submission status: Wrong Answer

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
N,K=MI()
a=[0]
for _ in range(N):
    a.append(int(I()))
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    ind=-1
    while i+ind>0:
        if abs(a[ind]-a[i])<=K:
            break
        ind-=1
    if i+ind==1:
        dp[i]=1
    else:
        dp[i]=dp[i+ind]+1
ans=0
for d in dp:
    if ans<d:
        ans=d
print(ans)

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 j != 1:
        j -= 1
        continue
    else:
        if i + j > len(A) - 1:
            break
        else:
            while flag:
                if i + j > len(A)-1:
                    flag = False
                else:
                    if abs(A[i]-A[i+j])<=K:
                        cnt += 1
                        flag = False
                    else:
                        j += 1

        
print(cnt)

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 + 2, 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 + 1):
        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())
A = [int(input()) for i in range(N)]
 
i_list = []
for i in range(N-1):
  for j in range(i+1,N):
    f = abs(A[j]-A[i])
    if f <= K:
      i_list.append(i)

print(i_list)
cnt = 1
first = i_list[0]
F = A[first]
for i in range(first+1,N):
  num = abs(A[i]-F)
  if num <= K:
    F = A[i]
    cnt +=1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = list(map(int,input().split()))
A = [int(input()) for i in range(N)]
if N == 1:
    print(1)
    exit()

lst = [-1]*(300001)
queue = deque()
queue.append((A[0],1,1))
lst[A[0]] = 1
while queue:
    # print(queue)
    r,size,i = queue.popleft()
    if i == N:
        continue
    if lst[r] <= size:
        if abs(r-A[i]) <= K:
            queue.append((A[i],size+1,i+1))
            lst[r] = size+1
        else:
            queue.append((r,size,i+1))
            lst[r] = size
print(max(lst))

Submission status: Wrong Answer

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

alist=[]
for _ in range(N):
  a=int(input())
  alist.append(a)
#print(alist)

now=alist[0]
seq_list=[0]
for i in range(1,N):
  if abs(alist[i]-now)<=K:
    now=alist[i]
    seq_list.append(i)
#print(seq_list)
#print(len(seq_list))

index1=seq_list[1]
answer=len(seq_list)

for j in range(1,index1):
  now=alist[j]
  seq_list=[j]
  for i in range(j+1,N):
    if abs(alist[i]-now)<=K:
      now=alist[i]
      seq_list.append(i)
      
  if answer<len(seq_list):
    answer=len(seq_list)
    
print(answer)

Submission status: Wrong Answer

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

print(len(a)-total)

Submission status: Wrong Answer

Solution code:
n,k,*L = map(int,open(0).read().split())
#print(L)
dp = [0] * n
dp[0] = 1

for i in range(n-1):
    if abs(L[i+1]-L[i]) <= k:
        dp[i+1] = dp[i] +1
    else:
        dp[i+1] = dp[i]

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = int(input())
ans = N
for i in range(N-1):
    b = int(input())
    if abs(a - b) > K:
        ans -= 1
    else:
        a = b
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-09-26 20:52:29 +0900
# LastModified: 2020-09-26 22:26:39 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import accumulate


def main():
    N, K = map(int, input().split())
    C = []
    for i in range(N):
        prev = int(input())
        C.append(prev)

    i = 1
    while i < len(C):
        if abs(C[i-1]-C[i]) <= K:
            i += 1
            pass
        else:
            C.pop(i)
    i = 1
    print(len(C))



if __name__ == "__main__":
    main()