该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P11388 [COCI 2024/2025 #1] 飞跃 / Skokovi

题目背景

译自 COCI 2024/2025 #1 T2。$\texttt{5s,0.5G}$。满分为 $75$。

题目描述

有 $n$ 朵花，此外有一个正整数 $k$。第 $i$ 朵花的高度为 $a_i$。

一开始，Filip 在第 $1$ 朵花上。

当她在第 $i$ 朵花上时，她可以飞跃到第 $j$ 朵花上，当且仅当：

• $i\lt j$；
• $|a_i-a_j|\le k$。

Filip 想要知道她能够飞跃到哪些花上。

输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。

输出格式

$n$ 个整数，第 $i$ 个整数为 $\texttt{0}$，代表不能跳到第 $i$ 朵花上；第 $i$ 个整数为 $\texttt{1}$，代表可以跳到第 $i$ 朵花上。

输入输出样例 #1

输入 #1

5 2
5 4 8 7 2

输出 #1

1 1 0 1 1

输入输出样例 #2

输入 #2

5 3
10 15 14 8 9

输出 #2

1 0 0 1 1

说明/提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• $1\le a_i,k\le 10^9$。

• 特殊性质 A：$\forall 1\le i\lt n$，$a_i\lt a_{i+1}$。

• #5694. 「COCI 2024/2025 #1」Skokovi

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #1 T2「Skokovi」

在某个不知名的地方，在一个不知名的世界里，住着一只名叫 Maya 的蜜蜂。她充满冒险的生活是任务构思的源泉，因此我们选择了其中的一个。

Maya 的朋友，一只名叫 Filip 的蚱蜢，正在备战花间跳跃奥运会。草地上的花朵可以用一个长度为 $N$ 的正整数序列 $a$ 来表示，每朵花的高度由数字 $a_{i}$ 给出。

Filip 总是从左向右跳跃。此外，由于这项运动对他来说是全新的，他无法跳到一朵与他当前所在花朵高度差过大的花上。具体来说，从第 $i$ 朵花，他可以跳到第 $j$ 朵花，当且仅当满足 $i < j$ 且 $|a_{i} - a_{j}| \leq K$，其中 $K$ 是输入中给定的正整数。

请通过确定 Filip 从最左侧的花朵出发可以到达哪些花朵，来帮助 Maya 规划 Filip 的训练。换句话说，对于每一朵花，确定是否存在一系列跳跃可以从第一朵花开始到达它。

输入格式

第一行包含正整数 $N$ $(1 \leq N \leq 2 \cdot 10^{5})$ 和 $K$ $(1 \leq K \leq 10^{9})$。

第二行包含一个正整数序列 $a$，即 $N$ 个数字 $a_{i}$ $(1 \leq a_{i} \leq 10^{9})$，表示花朵的高度。

输出格式

在一行中输出 $N$ 个数字，即 $0$ 或 $1$，每个数字表示对应的花朵是否可达。数字 $0$ 表示不可能到达该花朵，而 $1$ 表示该花朵是可达的。第一朵花总是可达的，因为 Filip 从那里开始跳跃。

样例 1

输入

5 2
5 4 8 7 2

输出

1 1 0 1 1

Filip 可以直接从第一朵花跳到第二朵花。第三朵花不可达，因为 Filip 无法从第一朵或第二朵花跳到它。为了到达第四朵花，Filip 也可以从第一朵花直接跳过去。对于最后一朵花，Filip 需要先跳到第二朵花，然后再跳到最后一朵花。

样例 2

输入

5 3
10 15 14 8 9

输出

1 0 0 1 1

数据范围与提示

详细子任务附加限制及分值如下表所示。