题目详情题解（0）讨论（0）提交记录（0）

AT_joi2025_yo2_d.親密なシェフ (Intimate Chef)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一家玻利维亚菜餐厅，有 NN 名厨师，每位厨师编号为 11 到 NN。第 ii 位厨师（1≤i≤N1 \leq i \leq N）可以制作美味度为 AiA_i 的 Silpancho 和美味度为 BiB_i 的 Pique Macho。

然而，由于厨师们性格各异，有 MM 对厨师关系不佳。第 jj 对关系不佳的厨师组合（1≤j≤M1 \leq j \leq M）为厨师 UjU_j 和厨师 VjV_j。

顾客在这家餐厅点餐的具体规则如下：

  • 顾客会选择满足 1≤p<q≤N1 \leq p < q \leq N 的整数 p,qp, q，要求厨师 pp 和厨师 qq 这两人出菜。不能选择关系不佳的厨师组合。
  • 对于两道菜 Silpancho 和 Pique Macho，每道菜都由这两位厨师中美味度更高的一位来制作。如果两人的美味度相同，则其中任意一人可以制作。需要注意，同一位厨师可以制作两道菜。
  • 顾客的满意度为两道菜的美味度之和。

现有 QQ 位编号为 11 到 QQ 的顾客来到餐厅。

第 kk 位顾客（1≤k≤Q1 \leq k \leq Q）会在可以选择的所有两人组合中，选择第 XkX_k 高的满意度的厨师两人组进行点餐。具体来说，设满意度为 SS，则根据 S×N2+p×N+qS \times N^2 + p \times N + q 从大到小排序，第 XkX_k 个为选择的 (pp, qq)。

给定所有厨师和顾客的信息，请编写程序计算第 kk 位顾客（1≤k≤Q1 \leq k \leq Q）的满意度。

输入格式

输入格式如下：

N M QN\ M\ Q
A1 A2 ⋯ ANA_1\ A_2\ \cdots\ A_N
B1 B2 ⋯ BNB_1\ B_2\ \cdots\ B_N
U1 V1U_1\ V_1
U2 V2U_2\ V_2
⋮\vdots
UM VMU_M\ V_M
X1 X2 ⋯ XQX_1\ X_2\ \cdots\ X_Q

输出格式

输出 QQ 行，每行输出一个整数，第 kk 行输出第 kk 位顾客的满意度。

输入输出样例

  • 输入#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 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1

    输出#2

    6

  • 输入#3

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

    输出#3

    9
7
7
10

  • 输入#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.（44 分）N≤50N \leq 50，M≤50M \leq 50，Q≤50Q \leq 50，Xk≤50X_k \leq 50（1≤k≤Q1 \leq k \leq Q）。
2.（99 分）Bi=1B_i = 1（1≤i≤N1 \leq i \leq N），M=0M = 0，Q=1Q = 1。
3.（1010 分）Bi=1B_i = 1（1≤i≤N1 \leq i \leq N），Q=1Q = 1。
4.（55 分）Bi=1B_i = 1（1≤i≤N1 \leq i \leq N）。
5.（2929 分）N≤100 000N \leq 100\,000，M≤100 000M \leq 100\,000，Q=1Q = 1，X1=1X_1 = 1。
6.（1414 分）N≤100 000N \leq 100\,000，M≤100 000M \leq 100\,000，Q=1Q = 1，X1≤100 000X_1 \leq 100\,000。
7.（1818 分）N≤100 000N \leq 100\,000，M≤100 000M \leq 100\,000，Q≤100 000Q \leq 100\,000，Xk≤100 000X_k \leq 100\,000（1≤k≤Q1 \leq k \leq Q）。
8.（1111 分）无其他附加约束。

样例解释 1

可以选择出菜的厨师两人组有 44 组，对应顾客的满意度如下：

  • 选择厨师 11 和厨师 22 时，Silpancho 由厨师 22 制作，Pique Macho 由厨师 11 制作。因此 Silpancho 的美味度为 77，Pique Macho 的美味度为 44，顾客满意度为 7+4=117 + 4 = 11。
  • 选择厨师 11 和厨师 44 时，两道菜均由厨师 44 制作。因此美味度分别为 55 和 88，满意度为 5+8=135 + 8 = 13。
  • 选择厨师 22 和厨师 33 时，Silpancho 由厨师 22 制作，Pique Macho 由厨师 33 制作，满意度为 7+4=117 + 4 = 11。
  • 选择厨师 33 和厨师 44 时，两道菜均由厨师 44 制作，美味度分别为 55 和 88，满意度为 5+8=135 + 8 = 13。

因此，各顾客的情况如下：

  • 顾客 11 选择的是厨师 33 和厨师 44，满意度是 1313。
  • 顾客 22 选择的是厨师 11 和厨师 44，满意度是 1313。
  • 顾客 33 选择的是厨师 22 和厨师 33，满意度是 1111。
  • 顾客 44 选择的是厨师 11 和厨师 22，满意度是 1111。

此输入例满足小数据范围 1,7,81,7,8 的约束。

样例解释 2

可以选择的厨师两人组合有 33 组，对应顾客满意度如下：

  • 选择厨师 11 和厨师 33 时，Silpancho 由厨师 33，Pique Macho 可由11或33制作，美味度分别为 55 和 11，合计满意度为 66。
  • 选择厨师 11 和厨师 44 时，Silpancho 由厨师 44，Pique Macho 可由11或44制作，美味度为 44 和 11，合计满意度为 55。
  • 选择厨师 33 和厨师 44 时，Silpancho 由厨师 33，Pique Macho 可由33或44制作，美味度均为 55 和 11，合计满意度为 66。

因此，顾客 11 选择的是厨师 33 和厨师 44，满意度为 66。

此输入例满足小数据范围 1,3,4,5,6,7,81,3,4,5,6,7,8 的约束。

样例解释 3

此输入例满足小数据范围 1,7,81,7,8 的约束。

样例解释 4

此输入例满足小数据范围 1,7,81,7,8 的约束。

数据范围与限制

  • 2≤N≤400 0002 \leq N \leq 400\,000。
  • 1≤Ai≤1091 \leq A_i \leq 10^9（1≤i≤N1 \leq i \leq N）。
  • 1≤Bi≤1091 \leq B_i \leq 10^9（1≤i≤N1 \leq i \leq N）。
  • 0≤M≤400 0000 \leq M \leq 400\,000。
  • M<N(N−1)2M < \frac{N(N - 1)}{2}。
  • 1≤Uj<Vj≤N1 \leq U_j < V_j \leq N（1≤j≤M1 \leq j \leq M）。
  • (Ui,Vi)≠(Uj,Vj)(U_i, V_i) \neq (U_j, V_j)（1≤i<j≤M1 \leq i < j \leq M）。
  • 1≤Q≤400 0001 \leq Q \leq 400\,000。
  • 1≤Xk≤400 0001 \leq X_k \leq 400\,000（1≤k≤Q1 \leq k \leq Q）。
  • Xk≤N(N−1)2−MX_k \leq \frac{N(N - 1)}{2} - M。
  • 所有输入的数均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页