問題一覧 > 通常問題

No.1170 Never Want to Walk

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 306
作問者 : opt / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 4387 / 自分の提出
問題文最終更新日: 2020-08-10 20:53:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 261 (順位表) の他の問題:

Problem Statement

There are $N$ stations on a number line. The coordinate of station $i$ $(1 \leq i \leq N)$ is $x_i$.

If the distance between station $i$ and station $j$ $(i \neq j)$ is at least $A$ and at most $B$, that is, if $A \leq |x_i - x_j| \leq B$, then you can travel between these $2$ stations by train in both directions. Otherwise, you cannot travel between them.

For each integer $i$ $(1 \leq i \leq N)$, find the number of stations that can be reached from station $i$ by using trains $0$ or more times.

Input

The input is given in the following format:

$N \quad A \quad B$
$x_1 \quad x_2 \quad \cdots \quad x_N$
  • All input values are integers
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A \leq B \leq 10^9$
  • $0 \leq x_1 < x_2 < \dots < x_N \leq 10^9$

Output

On the $i$-th line $(1 \leq i \leq N)$, output the number of stations that can be reached from station $i$ by using trains $0$ or more times. Output a newline at the end.

Sample

Sample 1
Input
5 4 6
0 2 5 7 8
Output
2
3
2
3
3

There are $3$ pairs of stations whose distance is at least $4$ and at most $6$: $(1, 3),$ $(2, 4),$ $(2, 5)$. You can travel only between these stations. You cannot travel on foot.

For example, from station $4$ you can reach stations $2, 4, 5$, so output $3$ on line $4$.

Sample 2
Input
10 37 45
2 8 11 13 19 30 38 50 61 92
Output
1
5
5
5
2
1
1
5
2
5

There may be isolated stations.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。