← 返回题目列表

AtCoder · joi2025_yo2_d

D. 贴心厨师

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

配点: 100 点

問題文

在一家玻利维亚餐厅 编号至 1 它们的编号最大为 N 编号最多为 N 厨师在那里工作。厨师 i (1 \leqq i \leqq N) 是美味是 A_i Silpancho 和美味 您可以制作一个 B_i 的 piquemacho。

然而,厨师很挑剔,和他相处得不好。 2 一群人 M 组。关系不好 2 人类组 j 番目 (1 \leqq j \leqq M) 是一名厨师 U_j 和厨师 V_j 的 2 这是一群人。

来这家餐厅的顾客吃的食物如下。 选择

  • 1 \leqq p < q \leqq N 的整数只有 p, q ,厨师 p 和厨师 q 的 2 请一群人做饭。然而我们关系并不好 2 你不能要求一群人为你做饭。
  • Silpancho和Piquemacho的每道菜都是由厨师准备的。 p 和厨师 q 是由一位能做出最美味的厨师制作的。关于某道菜 2 当两个人能做出一道味道一样的菜时,选哪一个? 1 由厨师制作。1 厨师 2 请注意,也可以制作两道菜。
  • 客户的満足度是Silpancho的美味和Piquemacho的美味的总和。

在这家餐厅 1 它们的编号最大为 Q 编号最多为 Q 店里来了很多顾客。

客 k (1 \leqq k \leqq Q)可以要求做饭。 2 在各组中,满意度为 X_k 最高 2 我请了一群人给我做饭。具体来说,满意 作为 S ,S \times N^2 + p \times N + q 是 X_k 最高厨师 p 和厨师 q (1 \leqq p < q \leqq N)的 2 我请了一群人给我做饭。

给定有关餐厅厨师和顾客的信息, 编写一个程序来查找 k (1 \leqq k \leqq Q的满意度。

制約

  • 2 \leqq N \leqq 400\,000.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N).
  • 0 \leqq M \leqq 400\,000.
  • M < \frac{N(N - 1)}{2}.
  • 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M).
  • (U_i, V_i) \neq (U_j, V_j) (1 \leqq i < j \leqq M).
  • 1 \leqq Q \leqq 400\,000.
  • 1 \leqq X_k \leqq 400\,000 (1 \leqq k \leqq Q).
  • X_k \leqq \frac{N(N - 1)}{2} - M (1 \leqq k \leqq Q).
  • 所有输入值都是整数。

小課題

  1. (4 点) N \leqq 50,M \leqq 50,Q \leqq 50,X_k \leqq 50 (1 \leqq k \leqq Q).
  2. (9 点) B_i = 1 (1 \leqq i \leqq N),M = 0,Q = 1.
  3. (10 点) B_i = 1 (1 \leqq i \leqq N),Q = 1.
  4. (5 点) B_i = 1 (1 \leqq i \leqq N).
  5. (29 点) N \leqq 100\,000,M \leqq 100\,000,Q = 1,X_1 = 1.
  6. (14 点) N \leqq 100\,000,M \leqq 100\,000,Q = 1,X_1 \leqq 100\,000.
  7. (18 点) N \leqq 100\,000,M \leqq 100\,000,Q \leqq 100\,000,X_k \leqq 100\,000 (1 \leqq k \leqq Q).
  8. (11 点)没有额外的限制。 在

入力

输入按以下格式给出。 输出

N M Q
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
X_1 X_2 \cdots X_Q

出力

Q 行输出。k 行目 (1 \leqq k \leqq Q) 有一位客户 输出 k 的满意度。


入力例 1

4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4

出力例 1

13
13
11
11

可以被要求准备菜肴的厨师。 2 人类群体是 4 有两种方法,每种方法的客户满意度如下。

  • 厨师 当你选择 1 和厨师 2 时,Silpancho就成为一名厨师。 由 2 创建,Piquemacho 是一名厨师 由 1 创建。因此,Silpancho的美味在于 7 Piquemacho的美味在于 4 变为。因此,顾客满意度是 7 + 4 = 11 。 在
  • 厨师 当你选择 1 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 8 变为。因此,顾客满意度是 5 + 8 = 13 。 在
  • 厨师 当你选择 2 和厨师 3 时,Silpancho就成为一名厨师。 由 2 创建,Piquemacho 是一名厨师 由 3 创建。因此,Silpancho的美味在于 7 Piquemacho的美味在于 4 变为。因此,顾客满意度是 7 + 4 = 11 。 在
  • 厨师 当你选择 3 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 8 变为。因此,顾客满意度是 5 + 8 = 13 。 在

因此,我们了解每个客户的以下信息。

  • 客 1 是一名厨师 3 和厨师 4 的 2 我选择了一群人。因此,客户 1 的满意度为 它变成了 13 。
  • 客 2 是一名厨师 1 和厨师 4 的 2 我选择了一群人。因此,客户 2 的满意度为 它变成了 13 。
  • 客 3 是一名厨师 2 和厨师 3 的 2 我选择了一群人。因此,客户 3 的满意度为 它变成了 11 。
  • 客 4 是一名厨师 1 和厨师 2 的 2 我选择了一群人。因此,客户 4 的满意度为 它变成了 11 。

此输入示例是一个小作业。 1,7,8 满足约束。


入力例 2

4 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1

出力例 2

6

可以被要求准备菜肴的厨师。 2 人类群体是 3 有两种方法,每种方法的客户满意度如下。

  • 厨师 当你选择 1 和厨师 3 时,Silpancho就成为一名厨师。 由 3 创建,Piquemacho 是一名厨师 由 1 卡厨师 3 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 1 变为。因此,顾客满意度是 5 + 1 = 6 。 在
  • 厨师 当你选择 1 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 1 卡厨师 4 创建。因此,Silpancho的美味在于 4 Piquemacho的美味在于 1 变为。因此,顾客满意度是 4 + 1 = 5 。 在
  • 厨师 当你选择 3 和厨师 4 时,Silpancho就成为一名厨师。 由 3 创建,Piquemacho 是一名厨师 由 3 卡厨师 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 1 变为。因此,顾客满意度是 5 + 1 = 6 。 在

因此,客户 我们了解以下有关 1 的信息。

  • 客 1 是一名厨师 3 和厨师 4 的 2 我选择了一群人。因此,客户 1 的满意度为 它变成了 6 。

此输入示例是一个小作业。 1,3,4,5,6,7,8 满足约束。


入力例 3

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

出力例 3

9
7
7
10

此输入示例是一个小作业。 1,7,8 满足约束。


入力例 4

13 12 10
2 28 28 60 48 77 63 92 13 71 36 91 87
85 7 64 15 55 92 66 91 83 35 49 22 61
2 9
8 13
7 11
9 11
8 12
5 12
4 7
11 12
10 12
4 11
1 5
3 8
49 21 46 13 20 41 6 33 24 7

出力例 4

121
169
129
174
169
137
183
148
169
183

此输入示例是一个小作业。 1,7,8 满足约束。