You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 JOI 2025 Final T1 「色塗り / Grid Coloring」

K 理事长正在制作一个由 $N$ 行 $N$ 列组成的网格图案。为此，他决定给每个格子涂上用整数编号表示的颜色。接下来，我们将从上往下的第 $i$ $(1 \le i \le N)$ 行，从左往右的第 $j$ $(1 \le j \le N)$ 列的格子称为格子 $(i, j)$。

目前，第 $1$ 列和第 $1$ 行的格子已经被涂上了颜色。具体来说，格子 $(i, 1)$ $(1 \le i \le N)$ 被涂成颜色 $A_i$，格子 $(1, j)$ $(1 \le j \le N)$ 被涂成颜色 $B_j$。这里 $A_1 = B_1$。

对于剩下的格子，K 理事长将按以下步骤进行填色：

• 依次处理 $i = 2, 3, \ldots, N$ 行的格子；
• 对于每一行依次处理 $j = 2, 3, \ldots, N$ 列的格子；
  • 将格子 $(i, j)$ 填上 $(i-1, j)$ 和 $(i, j-1)$ 这两个格子中颜色编号较大的颜色。如果两个格子的颜色编号相同，则使用相同的颜色。

K 理事长希望在所有 $N^2$ 个格子都填色完毕后，找到最多格子涂上的颜色编号，以及涂上该颜色的格子的数量。

给定网格的大小以及第 $1$ 列和第 $1$ 行的颜色信息，编写一个程序，求出涂上最多格子的颜色编号及其对应的格子数量。如果有多个颜色编号符合条件，请输出编号最大的颜色。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots A_N$。

第三行包含用空格分隔的 $N$ 个整数 $B_1, B_2, \ldots B_N$。

输出格式

输出涂上最多格子的颜色编号及其对应的格子数量。若存在多个颜色编号符合条件，则输出编号最大的颜色。

3
5 2 5
5 3 1

5 4

最终，每个格子的颜色编号如下：

$$\begin{array}{|l|l|l|} \hline 5 & 3 & 1 \\ \hline 2 & 3 & 3 \\ \hline 5 & 5 & 5 \\ \hline \end{array} $$

最多的颜色是 $5$，且涂在了 $4$ 个格子上，因此输出 $5$ 和 $4$。

这个样例满足子任务 $1,2,5$ 的限制。

3
1 7 8
1 3 5

8 3

最终，每个格子的颜色编号如下：

$$\begin{array}{|l|l|l|} \hline 1 & 3 & 5 \\ \hline 7 & 7 & 7 \\ \hline 8 & 8 & 8 \\ \hline \end{array} $$

最多的颜色是 $7$ 和 $8$，且分别涂在了 $3$ 个格子上。因为 $8$ 的编号较大，所以输出 $8$ 和 $3$。

这个样例满足子任务 $1,2,4,5$ 的限制。

4
2 1 2 1
2 1 1 2

2 10

这个样例满足子任务 $1,2,3,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \le N \le 200000$。
• $1 \le A_{i} \le 10^9$ $(1 \le i \le N)$。
• $1 \le B_{j} \le 10^9$ $(1 \le j \le N)$。
• $A_1 = B_1$。
• 输入的值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$15$	$N \le 500, A_{i} \le 100000\,(1 \le i \le N), B_{j} \le 100000\,(1 \le j \le N)$
$2$	$10$	$N \le 500$
$3$	$20$	$A_{i} \le 2\,(1 \le i \le N), B_{j} \le 2\,(1 \le j \le N)$
$4$	$25$	$A_{i}<A_{i+1}\,(1 \le i \le N-1), B_{j}<B_{j+1}\,(1 \le j \le N-1)$
$5$	$30$	无附加限制