레이팅 미적용In a land who knows where, in a world who knows when, lives a bee named Maya. Her adventure-filled
life is an endless source of ideas for tasks, so we chose one of them.
Maya’s friend, a grasshopper named Filip, is preparing for the Olympics in flower jumping. The flowers
in the meadow can be represented as a sequence of positive intergers \(a\) of length \(N\). The height of each
flower is given by the number \(a_{i}\).
Filip always jumps from left to right. Additionally, since this whole sport is new to him, he cannot jump
to a flower whose height differs too much from the one he is currently on. Specifically, from flower \(i\), he
can jump to flower \(j\) if and only if \(i < j\) and |\(a_{i} - a_{j}\)| ≤\(K\), where \(K\) is a positive integer given in the
input.
Help Maya plan Filip’s training by determining which flowers Filip can reach if he starts on the leftmost
flower. In other words, for each flower, determine if there is a sequence of jumps that leads to it, starting
from the first flower.
The first line contains positive intergers \(N\) (\(1 \le N \le 2 \cdot 10^{5}\)) and \(K\) (\(1 \le K \le 10^{9}\)).
The second line contains a sequence of positive intergers \(a\), i.e., \(N\) numbers \(a_{i}\) (\(1 \le a_{i} \le 10^{9}\)), representing
the heights of the flowers.
In a single line, output \(N\) numbers, either 0 or 1, where each number indicates whether the corresponding
flower is reachable. The number 0 means that it is not possible to reach that flower, while 1 means the
flower is reachable. The first flower is always reachable as Filip starts from there.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | Flower heights are strictly increasing. |
2 | 25점 | \(N \le 1\,000\) |
3 | 25점 | No additional constraints. |
5 2
5 4 8 7 21 1 0 1 15 3
10 15 14 8 91 0 0 1 1Clarification of the first example:
Filip can jump directly from the first flower to the second. The third flower is unreachable as Filip cannot
jump to it from either the first or the second flower. To reach the fourth flower, Filip can also jump
directly from the first flower. For the last flower, Filip needs to jump first to the second flower and then
to the last flower.