AT_joig2023_c 鐘 (Bell)

在 JOI 市有一条足够长的道路。可以将这条道路看作数轴，其中的每个位置都用一个实数坐标表示。 此外，JOI 市沿着这条道路有 $N$ 个钟，按照坐标从小到大的顺序标号为 $1$ 到 $N$。第 $i$ 个钟（$1 \leq i \leq N$）位于坐标 $A_i$。 在 JOI 市，每年年末会有让所有钟同时敲响的盛大活动。 每个钟敲响时，在该钟所在位置能听到音量为 $K$ 的声音；距离每远 $1$ 个单位，声音强度就减少 $1$，距离超过 $K$ 的地方声音强度为 $0$。也就是说，敲响第 $i$ 个钟时，在坐标 $x$ 能听到的其声音强度为 $\max\{K - |x - A_i|, 0\}$。其中，$|t|$ 表示 $t$ 的绝对值。 当所有钟一起敲响时，在坐标 $x$ 能听到的钟声强度为在该位置能听到的所有钟声强度中的最大值。 在 JOI 市沿着这条道路还住着 $M$ 户人家，按老到新顺序标号为 $1$ 到 $M$。第 $j$ 户人家（$1 \leq j \leq M$）住在坐标 $B_j$。 作为 JOI 市长，请你计算，所有钟一起敲响时，分别在 $B_1, B_2, \ldots, B_M$ 这些位置能听到钟声的强度。 现在给出 JOI 市的钟和住户信息，请编写程序，求出当所有钟同时敲响时，每个住户位置能听到的钟声强度。

输入按以下格式给出。 > $N$ $M$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$

输出 $M$ 行。第 $j$ 行（$1 \leq j \leq M$）输出在所有钟敲响时，住户 $j$ 所在坐标 $B_j$ 能听到的钟声强度。

## 小子任务 1. ($20$ 分) $N = 1$，$M \leq 1000$。 2. ($20$ 分) $N \leq 1000$，$M \leq 1000$。 3. ($60$ 分) 无其他条件。 ## 样例说明 1 在该输入例中，坐标 $20$ 处有第 $1$ 个钟。 - 敲响第 $1$ 个钟时，坐标 $20$ 能听到的钟声强度为 $\max\{10 - |20 - 20|, 0\} = 10$。因此，第 $1$ 行输出 $10$。 - 敲响第 $1$ 个钟时，坐标 $15$ 能听到的钟声强度为 $\max\{10 - |15 - 20|, 0\} = 5$。因此，第 $2$ 行输出 $5$。 - 敲响第 $1$ 个钟时，坐标 $28$ 能听到的钟声强度为 $\max\{10 - |28 - 20|, 0\} = 2$。因此，第 $3$ 行输出 $2$。 - 敲响第 $1$ 个钟时，坐标 $10$ 能听到的钟声强度为 $\max\{10 - |10 - 20|, 0\} = 0$。因此，第 $4$ 行输出 $0$。 - 敲响第 $1$ 个钟时，坐标 $32$ 能听到的钟声强度为 $\max\{10 - |32 - 20|, 0\} = 0$。因此，第 $5$ 行输出 $0$。 这个输入例满足所有小子任务的约束条件。 ## 样例说明 2 - 敲响第 $1,2,3$ 个钟时，在坐标 $57$ 能听到的音量分别为 $41,0,0$。因此所有钟同时敲响时，该位置能听到的最大音量为 $41$，第 $1$ 行输出 $41$。 - 敲响第 $1,2,3$ 个钟时，在坐标 $155$ 能听到的音量分别为 $61,61,0$。因此第 $2$ 行输出 $61$。 - 敲响第 $1,2,3$ 个钟时，在坐标 $222$ 能听到的音量分别为 $0,72,64$。因此第 $3$ 行输出 $72$。 - 敲响第 $1,2,3$ 个钟时，在坐标 $360$ 能听到的音量分别为 $0,0,0$。因此第 $4$ 行输出 $0$。 该输入例满足小子任务 $2, 3$ 的约束条件。 ## 样例说明 3 该输入例满足小子任务 $2, 3$ 的约束条件。 ## 数据范围与约束 - $1 \leq N \leq 250\,000$。 - $1 \leq M \leq 250\,000$。 - $1 \leq K \leq 10^9$。 - $0 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - $A_i < A_{i+1}$（$1 \leq i \leq N-1$）。 - $0 \leq B_j \leq 10^9$（$1 \leq j \leq M$）。 - $B_j \neq B_k$（$1 \leq j < k \leq M$）。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译