← 返回题目列表

Codeforces · 2230/E

E. 最小影响

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

假设您是新闻网站的所有者,想要研究某些选定的新闻项目如何影响您的用户。

你有 $$$n$$$ 条新闻,对于每条新闻,你已经确定了两个参数:它涉及政治 $$$p_i$$$ 的程度以及涉及文化 $$$c_i$$$ 的程度。

您还有 $$$m$$$ 用户对您想要研究的新闻的反应。对于每个人,你已经确定了三个参数:对政治新闻的容忍度$$$tp_j$$$,对文化新闻的容忍度$$$tc_j$$$,以及“影响范围”$$$d_j$$$。

新闻$$$i$$$中的政治$$$I_p(i, j)$$$和文化$$$I_c(i, j)$$$对用户$$$j$$$的影响可以通过以下公式计算:

$$\begin{array}{ c c } I_p(i, j) = \begin{cases} 0 & \text{if } p_i \lt tp_j \\ p_i & \text{if } tp_j \le p_i \lt tp_j + d_j \\ tp_j + d_j & \text{if } p_i \ge tp_j + d_j \end{cases}, & I_c(i, j) = \begin{cases} 0 & \text{if } c_i \lt tc_j \\ c_i & \text{if } tc_j \le c_i \lt tc_j + d_j \\ tc_j + d_j & \text{if } c_i \ge tc_j + d_j \end{案例} \end{数组}.$$

换句话说,虽然政治量$$$p_i$$$小于容忍水平$$$tp_j$$$,但它不会影响用户。否则,该主题会开始激怒用户,但不会超过 $$$tp_j + d_j$$$。文化也是如此。

新闻项$$$i$$$对用户$$$j$$$的总影响力为$$$I(i, j) = I_p(i, j) + I_c(i, j)$$$。

对于每个用户 $$$j$$$,确定 最小值 在所有新闻项$$$i$$$中影响$$$I(i, j)$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 新闻项的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le 10^6$$$) — 每条新闻的政治内容量。

第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 10^6$$$) — 每条新闻的文化内容量。

第四行包含一个整数 $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — 用户数量。

第五行包含 $$$m$$$ 整数 $$$tp_1, tp_2, \dots, tp_m$$$ ($$$0 \le tp_j \le 10^6$$$) — 每个用户的政治容忍度。

第六行包含 $$$m$$$ 整数 $$$tc_1, tc_2, \dots, tc_m$$$ ($$$0 \le tc_j \le 10^6$$$) — 每个用户的文化容忍度。

第七行包含 $$$m$$$ 整数 $$$d_1, d_2, \dots, d_m$$$ ($$$0 \le d_j \le 10^6$$$) — 每个用户的影响区域。

输出

对于每个用户,输出一个整数——所有新闻中的最小影响力 $$$I(i, j)$$$。

示例

输入
复制

6
2 4 1 6 0 10
3 2 6 1 9 0
5
0 0 0 1 5
0 0 9 5 2
9 4 8 2 2

输出
复制

5
4
1
2
2

输入
复制

5
75 19 53 12 10
34 75 67 84 95
5
55 14 46 97 14
78 61 56 23 33
10 4 7 11 3

输出
复制

0
18
53
34
36