← 返回题目列表

AtCoder · abc119_d

D. 懒惰的信仰

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

分数: 400 点

问题陈述

沿着一条东西方向的道路,有 A 神社和 B 寺庙。 的 i从西数第一个神社位于距离 s_i 距离道路西端米,并且 i从西数第一个寺庙位于距离 t_i 距离道路西端米。

回答以下问题 Q 查询:

  • 查询 i (1 \leq i \leq Q):如果我们从距离为 x_i 距离道路西端米,沿道路自由行驶,参观一神社一寺庙最少需要行驶多少距离? (允许通过超过规定数量的神社和寺庙。)

约束

  • 1 \leq A, B \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}
  • 1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}
  • 1 \leq x_i \leq 10^{10}
  • s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q 都是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

A B Q
s_1
:
s_A
t_1
:
t_B
x_1
:
x_Q

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

2 3 4
100
600
400
900
1000
150
2000
899
799

示例输出 1

350
1400
301
399

有两个神社和三个寺庙。这些神社的距离为 100, 600 距离道路西端 米,寺庙位于 400, 900, 1000 距离道路西端米。

  • 查询 1:如果我们从距离为 150 距离道路西端米,最佳移动方式是先步行 50 向西米去参拜神社,然后步行 300 米东参观寺庙。
  • 查询 2:如果我们从距离为 2000 距离道路西端米,最佳移动方式是先步行 1000 向西1米参观一座寺庙,然后步行 400 米西去参拜神社。途中我们会经过另一座寺庙,不过还好。
  • 查询 3:如果我们从距离为 899 距离道路西端米,最佳移动方式是先步行 1 向东一米参观寺庙,然后步行 300 米西去参拜神社。
  • 查询 4:如果我们从距离为 799 距离道路西端米,最佳移动方式是先步行 199 向西米去参拜神社,然后步行 200 米西去参观一座寺庙。

示例输入 2

1 1 3
1
10000000000
2
9999999999
5000000000

示例输出 2

10000000000
10000000000
14999999998

路很长,我们可能需要走一段不适合的距离 32位整数。