問題一覧 > 通常問題

No.1170 Never Want to Walk

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 212
作問者 : optopt / テスター : 37zigen37zigen
54 ProblemId : 4387 / 出題時の順位表
問題文最終更新日: 2020-08-10 20:53:36

問題文

数直線上に $N$ 個の駅があります. 駅 $i$ $(1 \leq i \leq N)$ の座標は $x_i$ です.

駅 $i$ と駅 $j$ $(i \neq j)$ の距離が $A$ 以上 $B$ 以下ならば,すなわち $A \leq |x_i - x_j| \leq B$ ならば,これら $2$ つの駅間を電車で双方向に移動できます. そうでないならば移動できません.

各整数 $i$ $(1 \leq i \leq N)$ に対し,駅 $i$ から電車を $0$ 回以上使って移動できる駅の数を求めてください.

入力

入力は以下の形式で与えられる:

$N \quad A \quad B$
$x_1 \quad x_2 \quad \cdots \quad x_N$
  • 入力は全て整数
  • $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$

出力

$i$ 行目 $(1 \leq i \leq N)$ に,駅 $i$ から電車を $0$ 回以上使って移動できる駅の数を出力せよ. 最後に改行を出力すること.

サンプル

サンプル1
入力
5 4 6
0 2 5 7 8
出力
2
3
2
3
3

距離が $4$ 以上 $6$ 以下である駅の組は $(1, 3),$ $(2, 4),$ $(2, 5)$ の $3$ つで,これらの駅間のみ移動できます. 徒歩移動はできません.

例えば,駅 $4$ からは駅 $2, 4, 5$ に移動できるため,$4$ 行目には $3$ と出力します.

サンプル2
入力
10 37 45
2 8 11 13 19 30 38 50 61 92
出力
1
5
5
5
2
1
1
5
2
5

孤立した駅が存在する場合もあります.

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