No.1170 Never Want to Walk
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
opt
37zigen