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:
def resolve():
    n, k = map(int, input().split())
    A = []
    dp = [0 for i in range(n)]
    dp[0] = 1
    for _ in range(n):
        A.append(int(input()))

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

    print(dp[-1])

resolve()

Submission status: Wrong Answer

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

tmp = A[0]
ans = 1
for i in range(1, N):
    a = A[i]
    if abs(tmp-a) <= K:
        ans += 1
        tmp = a
print(ans)

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, k, a_list):
    seg_tree = SegmentTree([0] * 300001, seg_func=max, seg_func_null=0)
    for i in range(n):
        a = a_list[i]
        r = seg_tree.query(max(0, a - k), min(a + k + 1, 300000))
        seg_tree.update(a, r + 1)
    return seg_tree.query(0, 300001)


def main():
    n, k = map(int, input().split())
    a_list = [int(input()) for _ in range(n)]
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(10, 3, [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]) == 7


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
class segment_tree():
    def __init__(self, N, function, b):
        #initialization
        self.n = N
        self.K = (N-1).bit_length()
        self.f = function
        self.b = b
        self.data = [b]*(1+ (1 << (self.K+1)))
        for i in range((1 << self.K)-1, 0, -1):
            self.data[i] = self.f(self.data[i << 1], self.data[i << 1 | 1])

    def update(self, k, value):
        # update a[k] = value
        k += 1 << self.K
        self.data[k] = value
        while k:
            k = k >> 1
            self.data[k] = self.f(self.data[k << 1], self.data[(k << 1) | 1])

    def query(self, L, R):
        #query [L,R)
        L += 1 << self.K
        R += 1 << self.K
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.data[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
ans = 0
seg_tree = segment_tree(6*10**5+1, max, 0)
for i, v in enumerate(A):
    ans = max(seg_tree.query(max(0, v-K), v+K+1) + 1, 1)
    seg_tree.update(v, ans)
print(ans)

Submission status: Wrong Answer

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

ss = [[0]]

for i in range(N):
  a = AS[i]
  f = False
  for s in ss:
    p = AS[s[-1]]
    if abs(a - p) <= K:
      s.append(i)
    else:
      f = True

  if f:
    ss.append([i])


print(max([len(ss[0])-1, *[len(s) for s in ss[1:]]]))

Submission status: Wrong Answer

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

A = [0]*n
cnt = 1

A[0] = int(input())
for i in range(1,n):
  A[i] = int(input())
  if abs(A[i-1] - A[i])<=k:
    #print(A[i-1],A[i])
    cnt+=1
  else:
    A[i]=A[i-1]
    
print(cnt)

Submission status: Wrong Answer

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

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
flag = False
for i in range(1, n):
    if abs(a[i] - b) <= k:
        ans += 1
        b = a[i]
        flag = True
    elif not flag:
        b = a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N,K=map(int, sys.stdin.readline().split())
A=[ int(sys.stdin.readline().strip()) for _ in range(N) ]
AA=[]
prev=None
for a in A:
    if prev is None:
        pass
    else:
        AA.append(a-prev)
    prev=a


t=0
ans=0
for a in AA:
    t+=a
    if abs(t)<=K:
        ans+=1
        t=0
ans+=1
print ans

Submission status: Wrong Answer

Solution code:
import sys


class SegmentTree:
    """
    https://qiita.com/dn6049949/items/afa12d5d079f518de368 から拝借しています。
    """

    def __init__(self, size, f=lambda x, y: max(x, y), default=0):
        self.size = 2 ** (size - 1).bit_length()
        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


input = sys.stdin.buffer.readline

N, K = map(int, input().split())
MAX = 300010
B = SegmentTree(MAX)
# 出現した値を管理する
for _ in range(N):
    a = int(input())
    m = B.query(max(1, a - K), min(MAX, a + K + 1))
    B.update(a, m + 1)
print(B.query(1, MAX))

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(input()) for i in range(N)]
B = []
for i in range(len(A)):
    if i == (len(A) - 1):
        break
    else:
        if A[i] + K >= A[i+1]:
            B.append(A[i])
        else:
            i += 1
print(len(B))

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 21:32:34 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    N, K = map(int, input().split())
    A = []
    for i in range(N):
        if i==0:
            prev = int(input())
        else:
            cur = int(input())
            A.append(abs(cur-prev))
            prev = cur
    ans = [a for a in A if a <= K]
    print(len(ans)+1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = []
A = int(input())
prev = A
for i, k in enumerate(range(1, N)):
  A = int(input())
  if abs(prev-A) <= 3:
    ans.append(prev)
    if k == N-1:
      ans.append(A)
    prev = A

print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys

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


def resolve():
    n, k = map(int, input().split())
    A = list(int(input()) for _ in range(n))

    C = []
    for i in range(1, n):
        C.append(abs(A[i] - A[i - 1]))

    res = 1
    for c in C:
        if c <= k:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
san = 300000
N,K = [int(a) for a in input().split()]
l = [0]*300000
for _ in range(N):
    a = int(input())
    M = 0
    for i in range(-3,4):
        if a+i>=0 and a+i<san: M= max(M,l[a+i-1])
    l[a-1]= M+1
print(max(l))

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)]
n = 300001

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

Submission status: Wrong Answer

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

ans = []
A = int(input())
prev = A
for i, k in enumerate(range(1, N)):
  A = int(input())
  if abs(prev-A) <= 3:
    ans.append(prev)
    if k == N-1:
      ans.append(A)
    prev = A

print(ans)

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(len(s)):
  if abs(s[pointer] - s[i]) <=w:
    ans.append(s[i])
    pointer=i

print(len(ans))

Submission status: Wrong Answer

Solution code:

def main():
    N, K = map(int, input().split())
    count = 1
    i = 1

    A = int(input())

    while i < N:
        Atemp = int(input())

        if abs(Atemp - A) <= K:
            count += 1
            A = Atemp

        i += 1
    
    print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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())
    for j in range(len(ans_list)):
        if abs(ans_list[j][-1] - A) <= K:
            ans_list[j].append(A)
            append_flag = True
    if not append_flag:
        ans_list.append([A])
    append_flag = False

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

print(max_length)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class segment_tree():
    def __init__(self, lists, function, b):
        #initialization
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = b
        self.data = [b]*(1+1 << (self.K+1))
        for i, v in enumerate(lists):
            self.data[i+ (1 << self.K)] = v
        for i in range((1 << self.K)-1, 0, -1):
            self.data[i] = self.f(self.data[i << 1], self.data[i << 1 | 1])

    def add(self, k, value):
        # add a[k] += value
        k += 1 << self.K
        self.data[k] += value
        while k:
            k = k >> 1
            self.data[k] = self.f(self.data[k << 1], self.data[(k << 1) | 1])

    def query(self, L, R):
        #query [L,R)
        L += 1 << self.K
        R += 1 << self.K
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.data[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
ans = [0 for i in range(N+1)]
seg_tree = segment_tree([0]*(6*10**5+1), max, -10**20)
for i, v in enumerate(A):
    ans[i+1] = max(seg_tree.query(max(0, v-K), v+K+1) + 1, 1)
    seg_tree.add(v, ans[i+1])
print(ans[N])

Submission status: Wrong Answer

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
INF=10**15
MAX_A=300000
G=segtree([0 for i in range(MAX_A+1)],max,-INF)
dp=[0 for i in range(N)]
dp[0]=1
for i in range(1,N):
    inf=max(0,A[i]-K)
    sup=min(MAX_A+1,A[i]+K+1)
    dp[i]=G.query(inf,sup)+1
    G.update(A[i],dp[i])
print(max(dp))

Submission status: Wrong Answer

Solution code:
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
memo:
GCD... INFをide_eleに設定して、片方がINFの場合はもう片方を返す
def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else return gcd(a,b)


vl = [1,4,6,8,9]

def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''

def main():
    vl = [0]*300001
    n,k = map(int, input().split())
    st = SegTree(vl,max,0)
    for _ in range(n):
        a = int(input())
        l = max(1,a-k)
        r = min(300001,a+k+1)
        curr_max = st.query(l,r)
        st.update(a,curr_max+1)

    ans = st.query(0,300001)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for i in range(1,N):
    if abs(A[i]-B[-1])<=K:
        B.append(A[i])
# print(B)
print(len(B))

Submission status: Wrong Answer

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

check = 0
b = []
b += [a[0]]
for num in range(len(a)-1):
    if abs(a[num] - a[num+1])  <= k:
      b += [a[num+1]]

print(len(b))

Submission status: Wrong Answer

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


c=[a[1]]
for i in a[2:]:
  if abs(int(c[-1])-int(i))<=k:
    c.append(i)

print(max(len(b),len(c)))

Submission status: Wrong Answer

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

print(max(cnt))

Submission status: Wrong Answer

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

for i in range(n):
    b = int(input())
    a.append(b)

b = a[0]

for i in range(n):
    if((abs(a[i] - b)) <= k):
        cnt += 1
        b = a[i]

print(cnt)

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, k, a_list):
    seg_tree = SegmentTree([0] * 300001, seg_func=max, seg_func_null=0)
    for i in range(n):
        a = a_list[i]
        r = seg_tree.query(max(0, a - k), min(a + k + 1, 300000))
        seg_tree.update(a, r + 1)
    return seg_tree.query(0, 300000)


def main():
    n, k = map(int, input().split())
    a_list = [int(input()) for _ in range(n)]
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(10, 3, [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]) == 7


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a=int(input())
l=[a]
x=[]
for i in range(n-1):
    tmp=int(input())
    l.append(tmp)
    x.append(tmp-a)
    a=tmp

total=0
ans=0
for i in x:
    total+=i
    if total<=k:
        total=0
        ans+=1
if n==1:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

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


import sys
input = sys.stdin.buffer.readline

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

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
b = [False]*n
ans = 0
for i in range(n-1):
    cnt = 1
    pre = a[i]
    if not b[i]:
        for j in range(i+1, n):
            if abs(pre-a[j]) <= k:
                cnt += 1
                pre = a[j]
                b[j] = True
        ans = max(ans, cnt)
    b[i] = True
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, AS):
    candidates = [[0]]
    for i in range(1, N):
        A = AS[i]
        new_candidates = []
        for c in candidates:
            if abs(AS[c[-1]] - A) <= K:
                new_candidates.append(c[:])
                c.append(i)
                new_candidates.append(c)
                break
            else:
                new_candidates.append(c)
        else:
            new_candidates.append([i])
        candidates = new_candidates
        candidates.sort(key=len, reverse=True)
        # debug("candidates", candidates)
    return len(candidates[0])


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

    print(solve(N, K, AS))


# tests
T1 = """
10 3
1
5
4
3
8
6
9
7
2
4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
7
"""

T2 = """
6 2
5
7
3
3
3
3
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
5
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Wrong Answer

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

for i in range(1,N):
    if abs(A[i]-A[i-1])<=K:
        B.append(A[i])
print(len(B))

Submission status: Wrong Answer

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

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

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

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

        self.num=k
        self.depth=d

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

        self.data=X

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

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

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

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

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


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

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

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

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

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

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

        if l==r:
            return r+index

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

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

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

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

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

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

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

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

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

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

print(DP[0])

Submission status: Wrong Answer

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