問題一覧 > 通常問題

No.1110 好きな歌

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 292
作問者 : trineutron / テスター : platinum
6 ProblemId : 3488 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 02:04:31

問題文

オリオン君には好きな歌がNN曲あり、曲i(1iN)i (1 \le i \le N)の好感度はAiA_iである。オリオン君は自分の感情を把握するのが苦手なので、AiAjDA_i - A_j \ge Dでないと曲iiの方が曲jjより好きだと認識できない。11からNNまでのiiそれぞれについて、曲iiの方が曲jjよりも好きだと認識するjjはいくつあるか求めよ。

入力

N DN\ D
A1A_1
A2A_2
\dots
ANA_N

1行目に曲数NNDDが与えられます。
続いてNN行、AiA_iが与えられます。

入力は全て整数
1N2×1051 \le N \le 2 \times 10^5
1D1091 \le D \le 10^9
1Ai1091 \le A_i \le 10^9

出力

NN行出力してください。ii行目にはAiAjD(1jN,ij)A_i - A_j \ge D (1 \le j \le N, i \ne j)となるようなjjの個数を出力してください。最後に改行してください。

サンプル

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

サンプル2
入力
1 1
9
出力
0

サンプル3
入力
10 3
3
1
4
1
5
9
2
6
5
3
出力
0
0
2
0
3
9
0
5
3
0

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