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:
import os
import sys
from io import BytesIO, IOBase

class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

def main():
    mxn = int(3e5)
    n, k = getints()
    a = []
    for _ in range(n):
        a.append(getint())
    st = SegmentTree([0] * mxn)
    for i in a:
        q = st.query(max(i - k, 0), min(mxn, i + k + 1))
        st[i] = q + 1
    print(st.query(0, n))


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def resolve():
  N, K = map(int, input().split(" "))
  checked_count = 0
  link_from = [[] for i in range(N)]
  link_to = [None] * N
  depth = [0] * N
  A = [0] * N

  # 入力
  for i in range(N):
    A[i] = int(input())

  # 接続を作る
  for i in range(N):
    next_index_diff = 1
    while i + next_index_diff < N:
      if abs(A[i] - A[i + next_index_diff]) <= K:
        link_from[i + next_index_diff].append(i)
        link_to[i] = i + next_index_diff
        break
      next_index_diff += 1

  # 逆順で幅優先探索
  max_val = 1
  num_checked_count = 0
  next_nodes = [N-1]
  count = [0] * N

  for i in reversed(range(N)):
    if link_to[i] is None:
      next_nodes = [i]
      while len(next_nodes) != 0:
        next_nodes_temp = []
        for node in next_nodes:
          num_checked_count += 1
          if link_to[node] is None:
            count[node] = 1
          else:
            count[node] += count[link_to[node]] + 1

          if count[node] > max_val:
            max_val = count[node]
          next_nodes_temp.extend(link_from[node])

        next_nodes = next_nodes_temp
    if num_checked_count >= N:
      break
  print(max_val)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

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

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-75), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Wrong Answer

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


new_list = []
new_list.append(list[0])

for i in range(N):
    if i + 1 == N:
        break
  
    did = abs(new_list[-1] - list[i + 1])
   
    if did <= K:
        new_list.append(list[i + 1])
        
if len(new_list) == 1:
    new_list.remove(new_list[0])
        
print(len(new_list))

Submission status: Wrong Answer

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

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-50), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Wrong Answer

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

dp = [1] * n

for i in range(n):
    for j in range(max(0, i-10), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 21
#scale = 3
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1)-1)
  maxi = 0
  now = [[l,r]]
  #print(now)
  for i in range(scale):
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
      #print(int(X<Y),X,maxi)
    #print(now,i)
  c += db[-1]
  maxi = max(maxi,seg[c])
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Submission status: Wrong Answer

Solution code:
def resolve():
  N, K = map(int, input().split(" "))
  checked_count = 0
  link_from = [[] for i in range(N)]
  link_to = [None] * N
  depth = [0] * N
  A = [0] * N

  # 入力
  for i in range(N):
    A[i] = int(input())

  # 接続を作る
  for i in range(N - 1):
    if link_to[i] is not None:
      continue

    next_index_diff = 1
    while i + next_index_diff < N:
      if abs(A[i] - A[i + next_index_diff]) <= K:
        link_from[i + next_index_diff].append(i)
        link_to[i] = i + next_index_diff
        break
      next_index_diff += 1

  # 逆順で幅優先探索
  max_val = 0
  num_checked_count = 0
  next_nodes = [N-1]
  count = [0] * N

  for i in reversed(range(N)):
    if link_to[i] is None:
      next_nodes = [i]
      while len(next_nodes) != 0:
        next_nodes_temp = []
        for node in next_nodes:
          num_checked_count += 1
          if link_to[node] is None:
            count[node] = 1
          else:
            count[node] += count[link_to[node]] + 1

          if count[node] > max_val:
            max_val = count[node]
          next_nodes_temp.extend(link_from[node])

        next_nodes = next_nodes_temp
    if num_checked_count >= N:
      break
  print(max_val)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
n,k = map(int,input().split())
N = 300000

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(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 not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
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] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; 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])
  #     print(data)

# 区間[l, r)内の最大値を求める
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

for i in range(n):
    a = int(input())
    update(max(0,a-k-1),min(N-1,a+k-1),1)
print(max(data))

Submission status: Wrong Answer

Solution code:
import random
import sys

sys.setrecursionlimit(1000000)
#n, k = map(int,input().split())
#a = [int(input()) for i in range(n)]
n = 300000
k = 300000
a = [random.randint(0,k) for i in range(n)]

def connect(i,d,p,q):
    if i+d >= n:
        if p > q:
            q = p
        #print("bbbb {} {}".format(p,q))
        return q

    if max(a[i] - a[i+d], a[i+d] - a[i]) <= k:
        #print("aaaa {} {}".format(p+1,q))
        q = connect(i+d,1,p+1,q)
    else:
        #print("aaaa {} {}".format(p,q))
        q = connect(i,d+1,p,q)

    return q

def main():
    #n,m,brg = input_1()
    #n,m,brg = input_2(300000,300000)

    ans = 0

    i = 0
    while i < (n - ans):
        q = connect(i,1,1,1)
        if q > ans:
            ans = q
        i += 1

    print(ans)


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
    group_list = defaultdict(int)
    group_list_ = []
    for i in range(N):
        a = I()
        A.append(a)
    for i in range(N):
        cnt = 0
        ans_list = [1]
        for j, group in enumerate(group_list_):
            if abs(group - A[i]) <= K:
                cnt = 1
                ans_list.append(group_list[group] + 1)
                group_list_[j] = A[i]
        if cnt == 0:
            group_list_.append(A[i])
        group_list[A[i]] = max(ans_list)
    ans = group_list.values()
    #print(group_list)
    print(max(ans))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


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

st = SegmentTree([N] * (max_A + 1), min, N)
edge = [set() for _ in range(N)]
for i, a in enumerate(reversed(A)):
    j = N - 1 - i
    p1 = st.get(a, min(max_A + 1, a + K + 1))
    if p1 < N:
        edge[j].add(p1)
    p2 = st.get(max(0, a - K), a)
    if p2 < N:
        edge[j].add(p2)
    p0 = st.get(a, a + 1)
    if p0 < N:
        edge[j].add(p0)
    st.update(a, j)

dp = [0] * N
dp[0] = 1
for i in range(N - 1):
    here = dp[i]
    for ni in edge[i]:
        if ni < N:
            dp[ni] = max(dp[ni], dp[i] + 1)

print(max(dp))

Submission status: Wrong Answer

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

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

        dp[i]=mx        

    print(max(dp))


main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a = [int(input()) for i in range(n)]
anslist=[1]*n
checklist=[]
for j in range(n):
    for l in range(j+1,n):
        if abs(a[j]-a[l])<=k:
            checklist.append([j,l])
            break


for m in checklist:
    if anslist[m[0]]>=anslist[m[1]]:
        anslist[m[1]]+=anslist[m[0]]

print(max(anslist))

Submission status: Wrong Answer

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

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

        dp[i]=mx        

    print(max(dp))


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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
    continue
  i += 1

print(len(A))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    # num_max = 3 * 10 ** 5
    A = [int(input()) for _ in range(N)]

    seen = [False] * N
    ans = 0
    for i in range(N):
        if seen[i]:
            continue
        last_num = A[i]
        seen[i] = True
        cnt = 1
        for j in range(i + 1, N):
            if abs(last_num - A[j]) <= K:
                last_num = A[j]
                seen[j] = True
                cnt += 1
        ans = max(ans, cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree, len(tree)

def update(i, x, tree, lt):
    i += lt // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(s, t, tree, lt):
    s += lt // 2
    t += lt // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n, k = map(int, input().split())
dp = [0] * n
t, lt = make_tree(300005)
for i in range(n):
    a = int(input())
    dp[i] = max(find(max(0, a - k), a, t, lt), find(a, min(300001, a + k), t, lt)) + 1
    update(a, dp[i], t, lt)
ans = dp[-1]
print(ans)

Submission status: Wrong Answer

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

# dp[i] iを含んで選んだときの最大個数
dp = [-1] * N
dp[0] = 0
for i in range(N-1):
    if abs(A[i]-A[i+1])<=K:
        dp[i+1] = max(dp[i+1],dp[i]+1)
    dp[i+1] = max(dp[i+1],dp[i])

print(max(dp)+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
n,k = map(int,input().split())
N = 300000

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(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 not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
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] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; 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])
  #     print(data)

# 区間[l, r)内の最大値を求める
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

for i in range(n):
    a = int(input())
    update(max(0,a-k-1),min(N-1,a+k-1),1)
print(query(0,300000-1))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools
imput = stdin.readline
n,k = map(int, input().split())  # 3個の数字の入力を受け取る
num_list = []
for i in range(n):
    num_list.append(list(map(int,input().split())))
#print(num_list)
num_list = list(itertools.chain.from_iterable(num_list))
#print(num_list)
count = 0
for i in range(n-1):
    count = count + 1
    countMax = 0
    if(abs(num_list[i]-num_list[i+1])>k):
        countTmp = count
        if(countMax<count):
            countMax = count
        count = 0
        
print(count)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 22
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1)-1)
  maxi = 0
  now = [[l,r]]
  for i in range(scale):
    #print(i,now)
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
    #print(len(now))
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Submission status: Wrong Answer

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

def init_max(init_max_val):
    #set_val
    for i in range(N):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = -1

lm = 300001

#num_max:n以上の最小の2のべき乗
num_max =2**(lm-1).bit_length()
seg_max=[ide_ele_max]*2*num_max



a = [0]*lm
init_max(a)

for _ in range(N):
    a = int(input())-1
    x = query_max(max(0, a-K), min(lm, a+K+1))
    update_max(a, x+1)

print(query_max(0, lm))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
scale = 21
seg = [0 for _ in range(2**scale)]
db = [2**i for i in range(scale)]
rdb = list(reversed(db))
#print(db)
#print(rdb)
#print(db)
for _ in range(n):
  c = int(input())
  l = max(c-k,0)
  r = min(c+k+1,2**(scale-1)-1)
  maxi = 0
  now = [[l,r]]
  for i in range(scale):
    #print(i,now)
    last = now
    now = []
    for xy in last:
      x,y = xy
      if x == y:
        continue
      X = (x-1) // rdb[i] + 1
      Y = y     // rdb[i]
      #print(x,y,X,Y,rdb[i])
      if X < Y:
        maxi = max(maxi,seg[db[i]+X])
        now.append([x,X*rdb[i]])
        now.append([Y*rdb[i],y])
      else:
        now.append(xy)
    #print(len(now))
  c += db[-1]
  while True:
    seg[c] = max(seg[c],maxi + 1)
    c //= 2
    if not c:
      break
  #print(seg)
print(seg[1])

Submission status: Wrong Answer

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

a=int(input())
temp=[a]
inf=10**6
lenss=[0]*inf
lenss[0]+=1
flag=True

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[None]*n
m=0
lian=0
a0=int(input())
a[0]=a0
for i in range(1,n):
  a1=int(input())
  a[i]=a1
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m:
      m=lian
    a0=int(a1)
m1=0
lian=0
a0=a[n-1]
for i in range(2,n+1):
  a1=a[n-i]
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m1:
      m1=lian
    a0=int(a1)
m2=0
lian=0
a0=a[n-2]
for i in range(3,n+1):
  a1=a[n-i]
  if a1-a0 >k:
    pass
  elif a0-a1>k:
    pass
  else:
    lian+=1
    if lian>m2:
      m2=lian
    a0=int(a1)
if m>m1:
  m1=m
  #print(m+1)
else:
  if m2>m1:
    m1=m2
print(m1)

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
N = 300001

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(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 is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
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] = x
        if L & 1:
            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])

# 区間[l, r)内の最大値を求める
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

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

for _ in range(n):
    x = int(input())
    MAX = query(max(0, x - k), min(300000, x + k + 1))
    update(x, x+1, max(query(x, x+1), MAX + 1))
print(query(0, 300000))

Submission status: Wrong Answer

Solution code:
x = []
x=map(int,input().split())
k = int(input())

y=list(x)

result = []

for i in y:
    if k>i:
        result.append(i)

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

lm = 300001

# N: 処理する区間の長さ
N0 = 2**(lm-1).bit_length()
INF = 0
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] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    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

for _ in range(N):
    a = int(input())
    x = query(max(0, a-K), min(lm, a+K+1))
    update(a, x+1)

print(query(0, N))

Submission status: Wrong Answer

Solution code:
"""
ACL0926_D
"""
import numpy as np

n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
b=[0]*n
c=[0]*n

b[0]=a[0]
a[0]=0

for i in range(1,n):
    for j in range(0,n-1):
        c[j]=abs(a[j]-b[i-1])
        if c[j]>k:
            c[j]=0
    max_index=np.argmax(c)
    b[i]=a[max_index]
    a[max_index]=0

for i in range(n):
    if b[i]==0:
        for j in range (i,j):
            b[j]=0
            
ans=np.count_nonzero(b)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=map(int,input().split())
A=int(input())
LIS = [A-1]
for i in range(N-1):
  A=int(input())
  if abs(A-1-LIS[-1])<=K:
    LIS.append(A-1)
  else:
    LIS[bisect.bisect_left(LIS, A)-1] = A-1

print(len(LIS))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = []
for i in range(n):
    a.append(int(input()))
b = sorted(a)
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

to = 0
sum = 1
for i in range(len(b)-1):
    if abs(b[i]-b[i+1]) <=k:
        sum += 1
    else:
        to = max(sum,to)
        sum = 0

print(max(len(a)-total,to))

Submission status: Wrong Answer

Solution code:

n, k = map(int, input().split())
al = []
for i in range(n):
    al.append(int(input()))
    
# N: 処理する区間の長さ
N = 300100
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]
    

update(0, 300100, (0, 0))
for idx, a in enumerate(al):
    now = query(a)
    left = max(0, a-k)
    right = min(300100, a+k)
    update(left, right+1, (idx+1, now+1))

ans = 0
for i in range(0, 300001):
    ans = max(ans, query(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n,k=map(int,input().split())
a=list(map(int,sys.stdin.read().split()))

dp=[1]*(n+10)
maxp=0
checked=[0]*(n+10)
for i in range(n):
  if checked[i]==1:
    continue
  for j in range(i+1,n):
    if abs(a[i]-a[j]) <= k:
      checked[j]=1
      if dp[j] < dp[i]+1:
        dp[j]=dp[i]+1
        if maxp < dp[j]:
          maxp=dp[j]
  
print(maxp)