CF2230E Minimum Influence

假设你是一家新闻网站的所有者，想要研究某些选定的新闻如何影响你的用户。 你有 $n$ 条新闻，每条新闻已经确定了两个参数：涉及政治的强度 $p_i$ 和涉及文化的强度 $c_i$。 你还有 $m$ 个用户，你想研究他们对新闻的反应。对于每个用户，你已经确定了三个参数：政治新闻的容忍度 $tp_j$、文化新闻的容忍度 $tc_j$ 以及“影响力区间” $d_j$。 新闻 $i$ 对用户 $j$ 的政治影响力 $I_p(i, j)$ 和文化影响力 $I_c(i, j)$ 可以通过以下公式计算： $$ \begin{array}{c c} I_p(i, j) = \begin{cases} 0 & \text{if } p_i < tp_j \\ p_i & \text{if } tp_j \le p_i < 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 < tc_j \\ c_i & \text{if } tc_j \le c_i < tc_j + d_j \\ tc_j + d_j & \text{if } c_i \ge tc_j + d_j \end{cases} \end{array}. $$ 换句话说，当政治强度 $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)$。

由 DeepSeek-V4 翻译