← 返回题目列表

AtCoder · joig2023_c

C. 贝尔

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI市有 1 本非常长的道路。这条道路可以看作数轴,每个地点用 1 个实数的坐标表示。

此外,JOI市沿这条道路有 N 个钟,按坐标从小到大排列,编号为 1 从 N 。钟 i (1 ≦ i ≦ N) 在坐标 A_i 。

在 JOI 市,1 年底同时敲响这些钟是一大活动。

无论哪个钟,敲响时在该钟同一地点能听到强度为 K 的声音,但随着距离 1 的增加,能听到的声音强度会 1 变小,当距离达到 K 时,强度为 0 。也就是说,当敲响钟 i 时,坐标 x 能听到的钟 i 的声音强度为 \max\{K - |x - A_i|, 0\} 。 其中,|t| 是 小于或等于 t 表示绝对值。

当所有的钟都被敲响时,坐标 x 能听到的钟声强度是坐标 x 所能听到的每个钟声强度的最大值。

JOI市沿着这条道路有 M 个房子,从旧到新的顺序编号为 1 从 M 。房子 j (1 ≦ j ≦ M) 在坐标 B_j 。

作为打飞机市的市长的你,希望在所有钟都敲响时,知道每个房子能听到的钟声强度。

给定JOI市的钟和房屋的信息时,当所有钟都敲响时,求出在坐标 B_1, B_2, …, B_M 的钟声强度的程序。

制約

  • 1 \leqq N \leqq 250\,000.
  • 1 \leqq M \leqq 250\,000.
  • 1 \leqq K \leqq 10^9.
  • 0 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • A_i \lt A_{i+1} (1 \leqq i \leqq N - 1).
  • 0 \leqq B_j \leqq 10^9 (1 \leqq j \leqq M).
  • B_j ≠ B_k (1 \leqq j < k \leqq M).
  • 所有输入值都是整数。

小課題

  1. (20 点) N = 1,M \leqq 1\,000.
  2. (20 点) N \leqq 1\,000,M \leqq 1\,000.
  3. (60 点)没有额外的限制。

入力

输入按以下格式给出。

N M K
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M

出力

M 按行输出。j 行目 (1 \leqq j \leqq M) 中,输出在所有钟都敲响时,坐标 B_j 的钟声强度。


入力例 1

1 5 10
20
20 15 28 10 32

出力例 1

10
5
2
0
0

在这个输入实例中,坐标 20 上有钟。 1 是

  • 鐘 1 时,坐标 20 能听到的钟 1 的声音强度为 \max\{10 - |20 - 20|, 0\} = 10 。因此,在坐标1 在线 写在方格 10 。
  • 鐘 1 时,坐标 15 能听到的钟 1 的声音强度为 \max\{10 - |15 - 20|, 0\} = 5 。因此,在坐标2 在线 写在方格 5 。
  • 鐘 1 时,坐标 28 能听到的钟 1 的声音强度为 \max\{10 - |28 - 20|, 0\} = 2 。因此,在坐标3 在线 写在方格 2 。
  • 鐘 1 时,坐标 10 能听到的钟 1 的声音强度为 \max\{10 - |10 - 20|, 0\} = 0 。因此,在坐标4 在线 写在方格 0 。
  • 鐘 1 时,坐标 32 能听到的钟 1 的声音强度为 \max\{10 - |32 - 20|, 0\} = 0 。因此,在坐标5 在线 写在方格 0 。

此输入示例满足所有子任务约束。


入力例 2

3 4 100
116 194 258
57 155 222 360

出力例 2

41
61
72
0
  • 鐘 1,2,3 时,坐标 57 能听到的声音强度分别为 41,0,0 。因此,当所有钟都被敲响时,在坐标 57 处听到的声音强度是这些最大值 41 。因此,1 在线 写在方格 41 。
  • 鐘 1,2,3 时,坐标 155 能听到的声音强度分别为 61,61,0 。因此,当所有钟都被敲响时,在坐标 155 处听到的声音强度是这些最大值 61 。因此,2 在线 写在方格 61 。
  • 鐘 1,2,3 时,坐标 222 能听到的声音强度分别为 0,72,64 。因此,当所有钟都被敲响时,在坐标 222 处听到的声音强度是这些最大值 72 。因此,3 在线 写在方格 72 。
  • 鐘 1,2,3 时,坐标 360 能听到的声音强度分别为 0,0,0 。因此,当所有钟都被敲响时,在坐标 360 处听到的声音强度是这些最大值 0 。因此,4 在线 写在方格 0 。

此输入示例是一个小作业。 2, 3 满足约束。 在


入力例 3

10 10 10000
589 2398 6567 28817 29177 31636 45468 66751 82282 97509
2196 54498 80474 61644 18007 38759 85590 72172 79533 69959

出力例 3

9798
970
8192
4893
0
3291
6692
4579
7251
6792

此输入示例是一个小作业。 2, 3 满足约束。 在