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:
# N: 処理する区間の長さ
N,k = map(int,input().split())

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,N-1))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

nums = [int(input()) for i in range(n)]

last_nodes = [n-1]
olast_nodes = []
first = True

while True:
    #print("last_nodes", last_nodes)
    cur_max_depth = 0
    for last_node in last_nodes:
        last_num = nums[last_node]

        node2depth = [None] * n
        node2depth[last_node] = 1
        depth2node = [None] + [[] for i in range(n)] 
        depth2node[1].append((last_node, last_num))
        cur_max_depth = 1

        for node1 in reversed(range(n-2)):
            found = False
            num1 = nums[node1]
            for fdepth in range(cur_max_depth, 0, -1):
                gnodes = depth2node[fdepth]
                for gnode, gnum in gnodes:
                    if abs(gnum-num1) <= k:
                        found = True
                        cur_depth = fdepth+1
                        depth2node[cur_depth].append((node1, num1))
                        cur_max_depth = max(cur_depth, cur_max_depth)
                        break
                if found:
                    break


            if not found:
                if first:
                    olast_nodes.append(node1)

    if first:
        first = False
        out = cur_max_depth
        last_nodes = olast_nodes
    else:
        out = max(cur_max_depth, out)
        break


#print(depth2node)


print(out)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split(' '))
a = [int(input()) for i in range(n)]
maxi = 0
check = [0 for i in range(n)]
start = []
for i in range(n):
  if check[i] == 0:
    for j in range(i+1, n):
      if abs(a[i]-a[j]) <= k:
        check[j] = -1
for i in range(n):
  if check[i] != -1:
    start.append(i)
#print(check, start)
for i in range(n):
  if len(start) == 0:
    break
  if i == start[0]:
    start.pop(0)
    temp = [a[i]]
    #print(temp, i)
    for j in range(i+1, n):
      #print(start, temp, i, j)
      if abs(temp[-1]-a[j]) <= k:
        temp.append(a[j])
    #print(temp)
    maxi = max(maxi, len(temp))
  else:
    continue
print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

def recursion(arr, length, idx, value, criteria, counta):
    if idx >= length:
        return counta
    if abs(arr[idx] - value) <= criteria:
        result_skip =  recursion(arr, length, idx + 1, value, criteria, counta)
        result_process = recursion(arr, length, idx + 1, arr[idx], criteria, counta+1)
        if result_skip >= result_process:
            return result_skip
        return result_process
    return recursion(arr, length, idx + 1, value, criteria, counta)
    
n, k = [int(i) for i in input().split()]
arr = [int(input()) for i in range(n)]

result = recursion(arr, n, 1, arr[0], k, 0)
print(result)

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, (1, now+1))

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

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=[]
for i in range(N):
    a.append(int(input()))
counter=0
b=a[0]
a.append(1000000)
for i in range(N):
    if abs(b-a[i+1])<K+1:
        b=a[i]
        counter+=1
print(counter+2)

Submission status: Wrong Answer

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

print(len(LIS))

Submission status: Wrong Answer

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

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

n , k = iia()
arr = []

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

Submission status: Wrong Answer

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


ans = n

for i in range(n):
  if i == 0:
    if abs(a[i]-a[i+1]) > k:
      ans -= 1
  elif 0 < i < n-1:
    if abs(a[i]-a[i+1]) > k:
      ans -= 1
  elif i == n-1:
    if abs(a[i]-a[i-1]) > k:
      ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

if N == 1:
    print(1)
    exit()

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

print(res+1)

Submission status: Wrong Answer

Solution code:
class LazySegmentTree():

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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, data[2*i-1], 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(data[R-1], x)
            if L & 1:
                lazy[L-1] = data[L-1] = max(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 bisect
N,K=map(int,input().split())
A=int(input())
LIS = [A]
for i in range(N-1):
  A=int(input())
  if abs(A-LIS[-1])<=3:
    LIS.append(A)
  else:
    LIS[bisect.bisect_left(LIS, A)-1] = A

print(len(LIS))

Submission status: Wrong Answer

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

a = 1
preA = int(input())
for i in range(N-1):
  A = int(input())
  if abs(A-preA)<=K:
    a += 1
    preA = A
   
print(a)

Submission status: Wrong Answer

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

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(300000, a+k)
    update(left, right+1, (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
sys.setrecursionlimit(1000000)

def recursion(arr, length, idx, value, criteria, counta):
    if idx >= length:
        return counta
    if abs(arr[idx] - value) <= criteria:
        result_skip =  recursion(arr, length, idx + 1, value, criteria, counta)
        result_process = recursion(arr, length, idx + 1, arr[idx], criteria, counta+1)
        if result_skip >= result_process:
            return result_skip
        return result_process
    return recursion(arr, length, idx + 1, value, criteria, counta)
    
n, k = [int(i) for i in input().split()]
arr = [int(input()) for i in range(n)]

result = max([recursion(arr, n, idx + 1, item, k, 0) for idx, item in enumerate(arr)])
print(result)

Submission status: Wrong Answer

Solution code:
class LazySegmentTree():

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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,N-1))

Submission status: Wrong Answer

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