시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB66484070.175%

문제

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 integers $N$ ($1 ≤ N ≤ 2 \cdot 10^5$) and $K$ ($1 ≤ K ≤ 10^9$). The second line contains a sequence of positive integers a, i.e., $N$ numbers $a_i$ ($1 ≤ a_i ≤ 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.

서브태스크

번호배점제한
120

Flower heights are strictly increasing.

225

$N ≤ 1\, 000$

325

No additional constraints.

예제 입력 1

5 2
5 4 8 7 2

예제 출력 1

1 1 0 1 1

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.

예제 입력 2

5 3
10 15 14 8 9

예제 출력 2

1 0 0 1 1

채점 및 기타 정보

  • 예제는 채점하지 않는다.