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:
#D
n, k = map(int, input().split())
used = [0]*n
a = []
#a = [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]
for i in range(n):
    temp = int(input())
    a.append(temp)


for i in range(n-1):
    if used[i]!=0: continue
    else:
        temp = a[i]
        c = i
        for j in range(i+1, n):
            if abs(temp-a[j])<=k:
                used[j]=max(used[j], used[c]+1)
                temp = a[j]
                c = j
print(max(used)+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a=[]
for i in range(n):
    a.append(int(input()))
    
dp= [0]*(n+1)
# dp[0]=1
maxa = 0

for i in range(1,n):
    tmp = 0
    for j in range(i,maxa-1,-1):
        if abs(a[i] - a[j]) <= k:
            tmp = max(tmp,dp[j])
        if maxa == tmp:
            dp[i]=tmp+1
            maxa+=1
            # print('break')
            break
    dp[i] = tmp + 1
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
from itertools import chain
N,K=map(int,input().split())
A=[int(input()) for _ in range(N)]
A_max = max(A)
A_min = min(A)
if A_max - A_min <= K:
    print(N)
    exit()

dp = [[0]*(N) for _ in range(2)] #len
top = [[0]*(N) for _ in range(2)] #top number

dp[0][0] = 0
dp[1][0] = 1
top[0][0] = -1
top[1][0] = A[0]
for i in range(1, N):
    if dp[0][i] < dp[0][i-1]:
        dp[0][i] = dp[0][i-1]
        top[0][i] = top[0][i-1]

    if abs(A[i] - top[0][i-1]) <= K or top[0][i-1] == -1:
        if dp[1][i] < dp[0][i-1] + 1:
            dp[1][i] = dp[0][i-1] + 1
            top[1][i] = A[i]
        # dp[0][i] = max(dp[0][i], dp[0][i-1])
        # dp[1][i] = max(dp[1][i], dp[0][i-1] + 1)

    if dp[0][i] < dp[1][i-1]:
        dp[0][i] = dp[1][i-1]
        top[0][i] = top[1][i-1]

    if abs(A[i] - top[1][i-1]) <= K:
        if dp[1][i] < dp[1][i-1] + 1:
            dp[1][i] = dp[1][i-1] + 1
            top[1][i] = A[i]
        
        # dp[0][i] = max(dp[0][i], dp[1][i-1])
        # dp[1][i] = max(dp[1][i], dp[1][i-1] + 1)
print(max(chain.from_iterable(dp)))

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
if abs(a[-1]-a[-2]) > k:
    total += 1
print(max(len(a)-total,total))

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
    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())
visited=[0]*n
li=[int(input()) for i in range(n)]
ans=0
for i in range(n):
    if visited[i]==0: #まだ訪れていない場合
        cnt=1
        x=li[i]
        for j in range(i+1,n):
            if abs(x-li[j])<=k:
                cnt+=1
                x=li[j]
                visited[j]=1
        ans=max(cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = float('inf')
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

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

n,k = map(int,input().split())
a = [int(input()) for i in range(n)]
m = max(a)

ind = [[] for i in range(m)]
for i,x in enumerate(a):
    ind[x-1].append(i)
seg_lis = []
for x in ind:
    if x == []:
        seg_lis.append(10**10)
    else:
        try:
            _ = len(x)
            seg_lis.append(x[0])
        except:
            seg_lis.append(x)


numbers = [0]*(m+1)

d = [0]*n

seg = SegTree(seg_lis, segfunc, ide_ele)
for i,x in enumerate(a):
    
    try:
        p = len(ind[x-1])
        numbers[x] += 1
        seg.update(x-1, ind[x-1][numbers[x]])
    except:
        seg.update(x-1, 10**10)
    
    low = x-1-k
    high = x-1+k
    if low < 0:
        low = 0
    if high >= m:
        high = m-1
    q1 = seg.query(x-1, high+1)
    
    q2 = seg.query(low, x)
    if q1 < 10**7:
        d[q1] = max(d[q1], d[i] + 1)
    if q2 < 10**7:
        d[q2] = max(d[q2], d[i] + 1)
print(max(d)+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
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
print(count_num+1)

Submission status: Wrong Answer

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

dp = [0] * (N + 1)
dp[1] = 1
m = 1
for i in range(2, N + 1):
    for j in reversed(range(max(1, i - 1000), i)):
        if abs(A[i] - A[j]) <= 3:
            if dp[j] == m:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])
                break
            else:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])

print(max(dp))

Submission status: Wrong Answer

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

ans = 0
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] > ans:
        ans = tmp[-1]
    if N - (i + 1) <= ans:
        break

print(ans)

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 = 1
for i in range(len(li)-1):
    if abs(li[i]-li[i+1]) <= k:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=[int(input()) for _ in range(N)]
ng=[0]
for i in range(1,N):
  if abs(A[i]-A[i-1])>K:
    ng.append(i)
ng.sort()
ans=0
for i in ng:
  cnt=1
  a=A[i]
  for j in range(i+1,N):
    if abs(A[j]-a)<=K:
      cnt+=1
      a=A[j]
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

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

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

A = []
for i in range(n):
    a = int(input())
    A.append(a)

ans = [0,A[0]]
for i in range(1,n):
    if A[i]-ans[-1] <= k:
        ans.append(A[i])
    else:
        ind = bisect.bisect_right(ans, A[i])
        if ind >= 0 and ind < len(ans):
            ans.insert(ind, A[i])
        else:
            if -ind-1 > len(ans)-1:
                if A[i] - ans[-1] <= k:
                    ans.append(A[i])
            else:
                if -ind-1 == 0:
                    ans.insert(-ind-1, A[i])
                elif A[i] - ans[-2] <= k:
                    ans.insert(-ind-1, A[i])
print(len(ans)-2)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
visited=[0]*n
li=[int(input()) for i in range(n)]
ans=0
for i in range(n):
    if visited[i]==0: #まだ訪れていない場合
        cnt=1
        x=li[i]
        t=[li[i]]
        for j in range(i+1,n):
            if abs(x-li[j])<=k:
                cnt+=1
                x=li[j]
                visited[j]=1
                t+=[li[j]]
        ans=max(cnt,ans)
print(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(1,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:
N, K = map(int, input().split())
A = [0] + [int(input()) for _ in range(N)]

dp = [0] * (N + 1)
dp[1] = 1
m = 1
for i in range(2, N + 1):
    for j in reversed(range(max(1, i - 100), i)):
        if abs(A[i] - A[j]) <= 3:
            if dp[j] == m:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])
                break
            else:
                dp[i] = max(dp[i], dp[j] + 1)
                m = max(m, dp[i])

print(max(dp))

Submission status: Wrong Answer

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

def main():
    n, k = map(int, input().split())
    alst = [int(input()) for _ in range(n)]
    N = 300100
    
    ll = - 10 ** 10    
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [ll]*(2*N0)
    
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v == ll:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = max(v, lazy[2*i-1], data[2*i-1], lazy[2*i], data[2*i])
            lazy[i-1] = ll
    
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)
    
        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = max(lazy[R-1], data[R-1], x)
            if L & 1:
                lazy[L-1] = data[L-1] = max(lazy[L-1], data[L-1], x)
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = max(data[2*i-1], data[2*i])
    
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r
    
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, data[R-1])
            if L & 1:
                s = max(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    ans = 0
    for a in alst:
        a += 50
        l = max(0,a - k)
        r = min(a + k, 300099)
        xx = query(a, a + 1) + 1
        update(l, r + 1, xx)
        ans = max(ans, xx)
    print(ans)
    
main()

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(300001, 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, 300000))

main()

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

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



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq

def main():
    N, K = MI()
    A = []
    dp = [0] * N
    dp[0] = 1
    for i in range(N):
        a = I()
        A.append(a)
    for i in range(1, N):
        x = -1
        for j in range(i - 1, -1, -1):
            if abs(A[j] - A[i]) <= K:
                x = j
                break
        if x == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = max(dp[x] + 1, dp[i - 1])
    print(dp[N - 1])
if __name__ == "__main__":
    main()

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:
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:
      count_num -= 1
      first += 1
if count_num <= 0:
  print(0)
else:
  print(count_num)

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, 3 * (10 ** 5) + 1)
    tmp = seg.query(low, high) + 1
    
    seg.update(a[i], tmp)
    
  print(seg.query(0, n))
  
main()

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
#if abs(a[-1]-a[-2]) > k:
#    total += 1
print(len(a)-total)

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)
arr1 = 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:
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
        #if shita==n-1:
        #    print(n-cut);exit()

print(n-cut)

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()))

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)+1
    r=i+k

    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:
n, k = map(int, input().split())
i = 0
z = 1
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:

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

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

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

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

N, K = map(int, input().split())
A = [int(input())-1 for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

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

Submission status: Wrong Answer

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

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

A = []
for i in range(n):
    a = int(input())
    A.append(a)

ans = [0,A[0]]
for i in range(1,n):
    if A[i]-ans[-1] <= k:
        ans.append(A[i])
    else:
        ind = bisect.bisect_left(ans, A[i])
        if ind >= 0 and ind < len(ans):
            ans.insert(ind, A[i])
        else:
            if -ind-1 > len(ans)-1:
                if A[i] - ans[-1] <= k:
                    ans.append(A[i])
            else:
                if -ind-1 == 0:
                    ans.insert(-ind-1, A[i])
                elif A[i] - ans[-2] <= k:
                    ans.insert(-ind-1, A[i])
print(len(ans)-2)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
a = int(input())
Alist = [a]
for i in range(N-1):
    anext = int(input())
    if abs(anext-a) <= K:
        Alist.append(anext)
        a = anext
    else:
        continue
print(len(Alist))

Submission status: Wrong Answer

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

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

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
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
if abs(a[-1]-a[-2]) > k:
    total += 1
print(len(a)-total)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

n, k = [int(i) for i in input().split()]
A = [int(input()) for j in range(n)]    # nは行数

tmp = [[A[0]]]
res = 1

for i in range(1, n):
    tmp_2 = []
    flg = False
    for j in tmp:
        if abs(j[-1] - A[i]) <= k:
            if len(j) >= len(tmp_2):
                tmp_2 = j
                flg = True
    if flg:
        tmp_2.append(A[i])
    else:
        tmp.append([A[i]])

for i in tmp:
    res = max(res, len(i))

print(res)

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

from collections import defaultdict
from bisect import bisect
n, k = list(map(int, input().split()))
al = [0] * n
for i in range(n):
    al[i] = int(input())
max_al = max(al)
min_al = min(al)
# N: 処理する区間の長さ
N = max(al)+1
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新


def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値


def query(l, r):
    L = l + N0
    R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1
        R >>= 1
    return s


for i in range(n):
    update(al[i], n)

for a in al:
    v = query(max(min_al, a-k), min(a+k+1, max_al))
    update(a, n-((n-v)+1))
v = query(min_al, max_al+1)
print(n-v+1)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n,k = ip()
x = [inp() for i in range(n)]
ct = 0
for i in range(n-1):
    if abs(x[i]-x[i+1]) > k:
        ct += 1
print(n-ct)