AT_abc119_d [ABC119D] Lazy Faith

题目描述

在一条东西方向延伸的道路旁，沿路建有 $A$ 家神社和 $B$ 座寺庙。从西端起第 $i$ 家神社位于距离道路西端 $s_i$ 米处，从西端起第 $i$ 座寺庙位于距离道路西端 $t_i$ 米处。

请回答以下 $Q$ 个问题。

第 $i$ 个问题（$1 \leq i \leq Q$）：如果从距离道路西端 $x_i$ 米的地点出发，并可以在道路上自由移动，访问一座神社和一座寺庙所需的最小移动距离是多少米？（途中可以经过多于一座神社或寺庙也没有关系。）

输入格式

输入通过标准输入按以下格式给出。

$A$ $B$ $Q$
$s_1$ $s_2$ $\ldots$ $s_A$
$t_1$ $t_2$ $\ldots$ $t_B$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个问题的答案。

样例 1

输入

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

输出

350
1400
301
399

样例 2

输入

1 1 3
1
10000000000
2
9999999999
5000000000

输出

10000000000
10000000000
14999999998

说明/提示

限制条件

• $1 \leq A, B \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq s_1 < s_2 < \ldots < s_A \leq 10^{10}$
• $1 \leq t_1 < t_2 < \ldots < t_B \leq 10^{10}$
• $1 \leq x_i \leq 10^{10}$
• $s_1, \ldots, s_A, t_1, \ldots, t_B, x_1, \ldots, x_Q$ 均互不相同。
• 所有输入值均为整数。

样例解释 1

有 $2$ 家神社和 $3$ 座寺庙，神社分别位于距离西端 $100,\ 600$ 米处，寺庙分别位于 $400,\ 900,\ 1000$ 米处。

• 问题 1：从距离西端 $150$ 米处出发，最优方案是先向西走 $50$ 米到神社，再向东走 $300$ 米到寺庙。
• 问题 2：从距离西端 $2000$ 米处出发，最优方案是先向西走 $1000$ 米到寺庙，再向西走 $400$ 米到神社。途中会经过一座寺庙，但没有关系。
• 问题 3：从距离西端 $899$ 米处出发，最优方案是先向东走 $1$ 米到寺庙，再向西走 $300$ 米到神社。
• 问题 4：从距离西端 $799$ 米处出发，最优方案是先向西走 $199$ 米到神社，再向西走 $200$ 米到寺庙。

样例解释 2

道路很长，可能需要移动的距离会超过 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译