← 返回题目列表

Codeforces · 1945/F

F. 基里尔和蘑菇

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

营地里的所有人都睡着了,基里尔就偷偷溜出帐篷,前往智慧橡树采集蘑菇。

已知橡树下生长着$$$n$$$蘑菇,每个蘑菇都具有魔力$$$v_i$$$。基里尔真的很想从蘑菇中制作出最大强度的魔法灵丹妙药。

丹药的强度等于其中蘑菇的数量与这些蘑菇中最小魔力的乘积。为了准备长生不老药,基里尔将依次采摘一颗生长在橡树下的蘑菇。基里尔可以按任意顺序采集蘑菇。

然而,事情并没有那么简单。智慧橡树告诉基里尔数字$$$p$$$从$$$1$$$到$$$n$$$的排列。如果基里尔只采摘 $$$k$$$ 蘑菇,那么所有指数为 $$$p_1, p_2, \dots, p_{k - 1}$$$ 的蘑菇的魔力将变为 $$$0$$$。基里尔不会用魔力为零的蘑菇来配制灵药。

你的任务是帮助基里尔采集蘑菇,以便他能够酿造出最大强度的灵丹妙药。然而,基里尔有点害怕在橡树附近停留太久,所以在所有适合采集蘑菇的选项中,他要求你找到蘑菇数量最少的一个。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$,但 $$$4$$$ 在数组中出现)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 蘑菇的数量。

第二行包含一个大小为 $$$n$$$ 的数组 $$$v$$$ ($$$1\le v_i \le 10^9$$$)——蘑菇的魔力。

第三行包含从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$p$$$。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出两个由空格分隔的整数——可以酿造的灵丹妙药的最大强度以及基里尔为此需要使用的最小蘑菇数量。

示例

输入 #1

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

输出 #1

16 2
9 3
8 2
20 2
5 1
20 2

注意

在第一个示例中,您需要获取索引为 $$$1$$$ 和 $$$2$$$ 的蘑菇,因此灵丹妙药的强度等于 $$$2 \cdot \min(a_1, a_2) = 2 \cdot \min(9, 8) = 2 \cdot 8 = 16$$$。注意,索引为$$$3$$$的蘑菇在采摘两个蘑菇后魔力会变成$$$0$$$。