C - Gap Existence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

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

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。

制約

  • 2 \leq N \leq 2\times 10^5
  • -10^9 \leq A_i \leq 10^9
  • -10^9 \leq X \leq 10^9
  • 入力は全て整数である

入力

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

N X
A_1 \ldots A_N

出力

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。

入力例 1

6 5
3 1 4 1 5 9

出力例 1

Yes

A_6-A_3=9-4=5 です。

入力例 2

6 -4
-2 -7 -1 -8 -2 -8

出力例 2

No

A_i-A_j=-4 となる組 (i,j) は存在しません。

入力例 3

2 0
141421356 17320508

出力例 3

Yes

A_1-A_1=0 です。

Score : 300 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • -10^9 \leq A_i \leq 10^9
  • -10^9 \leq X \leq 10^9
  • All values in the input are integers.

Input

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

N X
A_1 \ldots A_N

Output

Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.