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 main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    X=list(map(int,input().split()))
    N=X[0]
    K=X[1]
    A=[int(input()) for _ in range(N)]
    C=[0]*(N-1)
    j=1
    for i in range(N-1):
        C[i]=abs(A[i]-A[i+1])
        if C[i]<=K:
            j+=1
    print(j)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [[-1] for i in range(300010)]
d = [0] * N
for i in range(N):
    d[i] = int(input())
    A[d[i]].append(i)

c = [[0] * 2 for i in range(N)]

for i in range(N-1, -1, -1):
    del A[d[i]][-1]
    c[i][0] = max(A[d[i]][-1], A[d[i]-1][-1], A[d[i]-2][-1], A[d[i]-3][-1])
    c[i][1] = max(A[d[i]][-1], A[d[i]+1][-1], A[d[i]+2][-1], A[d[i]+3][-1])


dp = [1] * (N + 2)
ans = 0
for i in range(N-1, -1, -1):
    dp[c[i][0]] = dp[i] + 1
    dp[c[i][1]] = dp[i] + 1
    ans = max(ans, dp[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

N,K = I()
A = [k() for i in range(N)]
sum_a = itertools.accumulate(A)
dp = [0]*N
dp[0]=1

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
# cook your dish here
s=[int(i) for i in input().strip().split()]
n=s[0]
k=s[1]

l=[int(input()) for i in range(0,n)]
p=[]
#print(l)
for i in range(0,n-1):
    #print(abs(l[i+1]-l[i]))
    if(abs(l[i+1]-l[i])<=k):
        p.append(l[i])
print(len(p)+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[0]*n
dp=[0]*n
s=[]
for i in range(n):
  a[i]=int(input())
cnt=1
dp[0]=cnt
s.append(a[0])
for i in range(1,n):
  for j in range(len(s)):
    if abs(s[j]-a[i])<=k:
      cnt+=1
      dp[i]=cnt
      s=[]
      break
  s.append(a[i])
print(cnt)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = []
dp = [0 for _ in range(n + 1)]
dp[0] = 1
for i in range(n):
    _ = int(input())
    a.append(_)
for i in range(n - 1):
    if abs(a[i] - a[i + 1]) <= k:
        dp[i + 1] = dp[i] + 1
    else:
        dp[i + 1] = dp[i]
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)]

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:
from collections import deque
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
G = {i:[0,-1] for i in range(N)}
for i in range(N):
    for j in range(i+1,N):
        if abs(A[j]-A[i])<=K:
            G[i][1]=j
            G[j][0] += 1
            break
S = []
for i in range(N):
    if G[i][0]==0:
        S.append(i)
dist = [-1 for _ in range(N)]
for i in S:
    que = deque([(i,0)])
    dist[i] = 0
    while que:
        x,d = que.popleft()
        y = G[x][1]
        if y>=0 and dist[y]<d+1:
            dist[y]=d+1
            que.append((y,d+1))
dmax = max(dist)
print(dmax+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = []
t = []
l = -1

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

for i in range(n):
    cnt = 0
    if(l < a[i]):
        l = a[i]
        r = l
        for s in range(i,n):
            if((abs(a[s] - r)) <= k):
                cnt += 1
                r = a[s]
    t.append(cnt)

print(max(t))

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
ans=[]
for i in range(n):
    a=int(input())
    ans.append(a)
stack=[]
ma=[1]*(n+1)
for i in range(n-1,-1,-1):
    ma[i]=ma[i+1]
    while(stack and abs(ans[stack[-1]]-ans[i])<=k):
        c=stack.pop()
        if ma[c]+1>ma[i]:
            ma[i]=ma[c]+1
    stack.append(i)
print(ma[0])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
count = 0
for i in range(n):
  a = int(input())
  if i == 0:
    prev = a
  if abs(a - prev) <= k:
    if count == 0:
      if i != 0:
        count += 2
        #print(a, prev, end =" ")
    else:
      count += 1
      #print(a, end =" ")
  prev = a

print(count)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

N,K = I()
A = [k() for i in range(N)]
sum_a = itertools.accumulate(A)
dp = [0]*N

for i in range(1,N):
    if A[i]-A[i-1] <= K:
        dp[i] += dp[i-1]+1
    else:
        dp[i] = dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K = map(int,input().split())
A = []
for i in range(N):
    A.append(int(input()))
ls = []
l = 0
r = 1
B = deque(A)
if N == 1:
    print(0)
while len(B) > 0:
    e = B.popleft()
    ls.append(e)
    while len(B) > 0:
        q = B.popleft()
        if abs(e-q) <= K:
            B.appendleft(q)
            break
print(len(ls))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

t = [[] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(ans-1, -1, -1):
        idx = bisect_left(t[j], A[i])
        if idx != len(t[j]):
            if abs(t[j][idx] - A[i]) <= K:
                t[j+1].append(A[i])
                ans = max(ans, j+2)
                break
        elif idx > 0:
            if abs(t[j][idx-1] -A[i]) <= K:
                t[j+1].append(A[i])
                ans = max(ans, j+2)
                break
    else:
        t[0].append(A[i])
        ans = max(ans, 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

N,K = I()
A = [k() for i in range(N)]
sum_a = itertools.accumulate(A)
dp = [0]*N
print(dp)

for i in range(1,N):
    if A[i]-A[i-1] <= K:
        dp[i] += dp[i-1]+1
    else:
        dp[i] = dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

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

A = []

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

def abs(a):
    if a < 0:
        return -a
    return a

i = 1
while (i < N):
    
    if abs(A[i-1] - A[i]) > K:
        A.pop(i)
        N -= 1
    i += 1

print(len(A))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

N, K = list(map(int, sys.stdin.readline().strip().split(" ")))


data = []
for n in range(N):
    n = int(sys.stdin.readline().strip())
    if len(data) == 0:
        data.append([n])
    else:
        checked = [True] * len(data)
        for i, d in enumerate(data):
            if abs(n - d[-1]) <= K:
                data[i].append(n)
            else:
                checked[i] = False
        lens = []
        for i, c in enumerate(checked):
            if c:
                lens.append(len(data[i]))
            else:
                lens.append(-1)
        if len(lens) > 1:
            m = -1
            mi = -1
            for i, l in lens:
                if m < l:
                    m = l
                    mi = i
            data = [d for i, d in enumerate(data) if not (checked[i] and lens[i] != m)]


print(max([len(d) for d in data]))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K = map(int,input().split())
A = []
for i in range(N):
    A.append(int(input()))
ls = []
l = 0
r = 1
B = deque(A)
if N == 1:
    print(1)
while len(B) > 0:
    e = B.popleft()
    ls.append(e)
    while len(B) > 0:
        q = B.popleft()
        if abs(e-q) <= K:
            B.appendleft(q)
            break
print(len(ls))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K = map(int,input().split())
A = []
for i in range(N):
    A.append(int(input()))
ls = []
l = 0
r = 1
B = deque(A)
if N == 1:
    print(1)
while len(B) > 0:
    e = B.popleft()
    ls.append(e)
    while len(B) > 0:
        q = B.popleft()
        if abs(e-q) <= K:
            B.appendleft(q)
            break
print(ls)
print(len(ls))

Submission status: Wrong Answer

Solution code:

n, k = (int(x) for x in input().split())

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

# print(a_list)

ans = 1
b = a_list[0]

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

print(ans)

Submission status: Wrong Answer

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


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



dp=[0]*3*10**5
seg=SegmentTree(dp, max, 0)
for i in range(N):
    a=int(input())
    if i==0:
        seg.update(a-1,1)
    else:
        left=max(0, a-K-1)
        right=min(N, a+K)
        now=seg.query(left, right)
        seg.update(a-1, now+1)

print(seg.query(0,N))

Submission status: Wrong Answer

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

B = []
for idx, a in enumerate(A):
  if idx == 0:
    tmp = a
    B.append(a)
    continue
  if abs(tmp - a) <= K:
    B.append(a)
    tmp = a

print(len(B))

Submission status: Wrong Answer

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

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

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


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

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

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

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

    return arr


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


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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

    divisors.sort()
    return divisors

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

# segment tree

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

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

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

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



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

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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()

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

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):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

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

    def query(self, l, r):
        res = self.ide_ele

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

size = 10**5*3+10
seg = SegTree([0]*size, segfunc, ide_ele)
for _ in range(N):
    a = int(input())
    maxi = seg.query(max(0, a-K-1), min(size, a+K))
    seg.update(a-1, maxi+1)
print(seg.query(0, size))

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)]
y = [x[0]]
for i in range(1,n):
    if abs(x[i]-y[-1]) <= k:
        y.append(x[i])
print(len(y))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
bigger = [(A[0], 1)]
smaller = [(A[0], 1)]
for a in A[1:]:
    temp = []
    while bigger and abs(a - bigger[0][0]) <= K:
        prev, length = heappop(bigger)
        temp.append((a, length + 1))
    for item in temp:
        heappush(bigger, item)
    temp = []
    while smaller and abs(a - smaller[0][0]) <= K:
        prev, length = heappop(smaller)
        temp.append((a, length + 1))
    for item in temp:
        heappush(smaller, item)
print(max(max(length for _, length in bigger),
          max(length for _, length in smaller)))

Submission status: Wrong Answer

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

t = deque([(1, AS[0])])

for i in range(1, N):
  cnt, lst = t[i-1]
  if abs(lst - AS[i]) <= K:
    t.append((cnt + 1, AS[i]))
  else:
    t.append((cnt, lst))

print(t[N-1][0])

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = inplm(n)
AA = []
for i in range(1,n):
    AA.append(A[i] - A[i-1])

s = 0
cnt = 0
for aa in AA:
    if abs(s + aa) > k:
        s += aa
        cnt += 1
    else:
        s = 0

print(n - cnt)

Submission status: Wrong Answer

Solution code:
#from collections import deque, Counter
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#from decimal import Decimal
#mod = 1000000007
#mod = 998244353
#N = int(input())
#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################
 
#####ide_ele#####
ide_ele = -1
#################
 
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



### https://qiita.com/ell/items/fe52a9eb9499b7060ed6 heapについて　最大最小の取り出し
N, K = map(int, input().split())
tree = [0 for _ in range(400000)]
tree = SegTree(tree, segfunc, ide_ele)
for k in range(N):
  A = int(input())
  A -= 1
  n = tree.query(max(0, A-K), min(400000, A+K+1))
  tree.update(A, n+1)
print(tree.query(0, 400000))
#A = list(map(int, input().split()))
#flag = True
#for k in range(N):
#ans = 0
#print(ans)
#print('Yes')
#print('No')

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
ans=[0]
xlis=[]
for i in range(n):
    x=int(input())
    xlis.append(x)
ave=sum(xlis)/n
ind=0
for i in range(n):
    x=xlis[i]
    if(x+ans[ind-1]>100*ave):
        continue
    if(ind==0):
        ans[0]=x
        ind+=1
        continue
    if(abs(x-ans[ind-1])<=k):
        ans.append(x)
        ind+=1
print(ind)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(input()) for _ in range(n)]
s = set()
ans = 0
for i in range(n):
  cnt = 1
  tmp = a[i]
  for j in range(i+1,n):
    if j in s:
      break
    if abs(a[j]-tmp)<=k:
      cnt += 1
      tmp = a[j]
      s.add(j)
  ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[0]*n
dp=[0]*n
s=[]
for i in range(n):
  a[i]=int(input())
cnt=1
dp[0]=cnt
s.append(dp[0])
for i in range(1,n):
  for j in range(len(s)):
    if abs(s[j]-a[i])<=k:
      cnt+=1
      dp[i]=cnt
      s=[]
      break
  s.append(a[i])
print(cnt)

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 = [int(input()) for _ in range(N)]
DP = [1] + [0] * (N-1)

for i in range(1,len(A)):
  if abs(A[i-1]-A[i]) <= K:
    DP[i] += DP[i-1] + 1
  else:
    DP[i] = DP[i-1]

print(DP[N-1])

Submission status: Wrong Answer

Solution code:
import collections
n,k = map(int,input().split())
ls = [int(input()) for i in range(n)]
p = 0
al = []
for i in range(n):
    p += i
    for j in range(p+1,n):
        if abs(ls[p]-ls[j]) <= k:
            al.append(ls[p])
            al.append(ls[j])
            p = j-i-1
            break
            
c = collections.Counter(al)
print(len(c))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a=[]
amax =0
acount =0
for i in range(n):
  a.append(int(input()))
  if i > 0:
    if abs(a[i]-a[i-1]) <= 3:
      #print(a[i])
      acount +=1
  else:
      #print(a[i])
      acount += 1
print(acount)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
tmp = int(input())
x.append(tmp)
for i in range(n-1):
  t = int(input())
  if abs(t-tmp) <= k:
    x.append(t)
    tmp = t
print(len(x))

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().rstrip().split())
a = [0]*n
for i in range(n):
    a[i] = int(input())
b = [a[0]]
now = a[0]
second = -1
for i in range(1,n):
    if abs(now-a[i])<=k:
        b.append(a[i])
        now = a[i]
        if second == -1:
            second = i
l = [len(b)]
for i in range(1,second):
    b = [a[i]]
    now = a[i]
    for j in range(i+1,n):
        if abs(now-a[j])<=k:
            b.append(a[j])
            now = a[j]
    l.append(len(b))
print(max(l))

Submission status: Wrong Answer

Solution code:

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

l = [int(input()) for _ in range(n)]
l2 = []

for i in range(len(l)-1):
    if abs(l[i] - l[i+1]) > k:
        l.pop(i+1)
        l.append(3000001)

a = l.index(3000001)

l = l[:a]

print(len(l))

Submission status: Wrong Answer

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

if (len(a) == 1):
  print(1)
  exit()
if (len(a) == 2):
  if abs(a[0] - a[1])  > k:
    print(1)
  else:
    print(2)
  exit()
ch = 0
while (ch < len(a)-1):
  #print(a,ch)
  if abs(a[ch] - a[ch+1])  > k:
    a.pop(ch+1)
    ch -= 1
  ch += 1

print(len(a))

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().rstrip().split())
a = [0]*n
for i in range(n):
    a[i] = int(input())
b = [a[0]]
now = a[0]
second = -1
for i in range(1,n):
    if abs(now-a[i])<=k:
        b.append(a[i])
        now = a[i]
        if second == -1:
            second = i
l = [len(b)]
for i in range(1,second):
    b = [a[i]]
    now = a[i]
    for j in range(i+1,n):
        if abs(now-a[j])<=k:
            b.append(a[j])
            now = a[j]
    l = [len(b)]
print(max(l))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,k=map(int,input().split())
n=300_002
def update(i,x):#A[i]=x
	now=2**deep+i
	seg[now-1]=x
	while now>1:
		now//=2
		seg[now-1]=min(seg[now*2-1],seg[now*2])
def minimum(x,y):#A[x]からA[y]の最小値	
	s=inf
	l=x+2**deep
	r=y+2**deep+1
	while l<r:
		if l%2==1:
			s=min(s,seg[l-1])
			l+=1
		if r%2==1:
			r-=1
			s=min(s,seg[r-1])
		l//=2
		r//=2
	return s
inf=0
deep=(n-1).bit_length()
seg=[inf]*(2**deep*2-1)
for i in range(N):
	a=int(input())
	x=max(a-k-1,0)
	y=min(a+k-1,n)
	update(a-1,minimum(x,y)-1)
print(-minimum(0,n-1))

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(300000)], segfunc, ide_ele)

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

print(seg.query(0, 300000))

Submission status: Wrong Answer

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

def count(list):
    pre = list[0]
    ls.clear()
    for i in range(1,len(list)):
        if abs(pre-list[i]) <= K:
            pre = list[i]
        else:
            ls.append(list[i])
    #print(list,ls)

count(A)
while 1:
    if len(A)-len(ls) >= len(ls):
        print(len(A)-len(ls))
        break
    else:
        A = ls
        count(A)