E - Smooth Subsequence

Contest Duration: 2024-02-03(Sat) 12:00 - 2024-02-03(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Smooth Subsequence Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $525$ 点

問題文

長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。

$A$ の部分列であって、隣接する $2$ 項の差の絶対値が $D$ 以下であるようなものの長さの最大値を求めてください。

ただし、数列 $A$ の部分列とは、 $A$ の要素を $0$ 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。

制約

$1 \leq N \leq 5 \times 10^5$
$0 \leq D \leq 5 \times 10^5$
$1 \leq A_i \leq 5 \times 10^5$
入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $D$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

出力

答えを出力せよ。

入力例 1Copy

Copy

4 2
3 5 1 2

出力例 1Copy

Copy

$A$ の部分列 $(3, 1, 2)$ は隣接する $2$ 項の差の絶対値が $2$ 以下です。

入力例 2Copy

Copy

5 10
10 20 100 110 120

出力例 2Copy

Copy

入力例 3Copy

Copy

11 7
21 10 3 19 28 12 11 3 3 15 16

出力例 3Copy

Copy

Score: $525$ points

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$ .

Find the maximum length of a subsequence of $A$ such that the absolute difference between any two adjacent terms is at most $D$ .

A subsequence of a sequence $A$ is a sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order.

Constraints

$1 \leq N \leq 5 \times 10^5$
$0 \leq D \leq 5 \times 10^5$
$1 \leq A_i \leq 5 \times 10^5$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $D$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

Output

Print the answer.

Sample Input 1Copy

Copy

4 2
3 5 1 2

Sample Output 1Copy

Copy

The subsequence $(3, 1, 2)$ of $A$ has absolute differences of at most $2$ between adjacent terms.

Sample Input 2Copy

Copy

5 10
10 20 100 110 120

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

11 7
21 10 3 19 28 12 11 3 3 15 16

Sample Output 3Copy

Copy