Cowmpetency

题目描述

Farmer John 正在为他的奶牛招聘一位新的牛群领袖。为此，他面试了 $N$（$2 \leq N \leq 10^5$）头奶牛来竞争该职位。在面试完第 $i$ 位候选者后，他会给这头奶牛分配一个整数“cowmpetency”分数 $c_i$，范围为 $1$ 到 $C$（含端点）（$1 \leq C \leq 10^9$），该分数与其领导能力相关。

由于面试的奶牛太多，Farmer John 记不住所有奶牛的 cowmpetency 分数。不过，他记得 $Q$（$1 \leq Q < N$）对数 $(a_j, h_j)$，其中奶牛 $h_j$ 是第一头 cowmpetency 分数严格大于奶牛 $1$ 到 $a_j$ 的奶牛（因此 $1 \leq a_j < h_j \leq N$）。

现在 Farmer John 告诉你序列 $c_1, \dots, c_N$（其中 $c_i = 0$ 表示他忘记了第 $i$ 头奶牛的 cowmpetency 分数）以及这 $Q$ 对 $(a_j, h_j)$。请你帮助他确定与这些信息一致的、字典序最小的 cowmpetency 分数序列，或者判断不存在这样的序列！如果两个分数序列在第一个不同的位置上，一个序列给该奶牛分配的分数更小，则该序列字典序更小。

每个输入包含 $T$（$1 \leq T \leq 20$）个相互独立的测试用例。保证所有测试用例的 $N$ 之和不超过 $3 \cdot 10^5$。

输入格式

第一行包含 $T$，表示独立测试用例的数量。每个测试用例如下：

首先一行包含 $N$、$Q$ 和 $C$。

接下来一行包含序列 $c_1, \dots, c_N$（$0 \leq c_i \leq C$）。

最后有 $Q$ 行，每行包含一对 $(a_j, h_j)$。保证在同一个测试用例中所有 $a_j$ 两两不同。

输出格式

对于每个测试用例，输出一行：给出与 Farmer John 记忆一致的字典序最小的 cowmpetency 分数序列；如果不存在这样的序列，则输出 $-1$。

1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

1 2 2 3 4 4 1

5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9

1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1

提示

我们可以看到给定输出满足 Farmer John 记得的所有数对。 $\max(c_1) = 1$，$c_2 = 2$ 且 $1<2$，所以第一对满足 $\max(c_1,c_2,c_3) = 2$，$c_4 = 3$ 且 $2<3$，所以第二对满足 $\max(c_1,c_2,c_3,c_4) = 3$，$c_5 = 4$ 且 $3<4$，所以第三对满足

还有若干其他与 Farmer John 记忆一致的序列，例如 1 2 2 3 5 4 1 1 2 2 3 4 4 5 但这些都不比给定输出的字典序更小。

在测试用例 3 中，由于 $C=1$，唯一可能的序列是 1 1 然而在这种情况下，奶牛 2 的分数并不大于奶牛 1，因此无法满足条件。

在测试用例 5 中，$a_1$ 和 $h_1$ 告诉我们奶牛 6 是第一头分数严格大于奶牛 1 到 4 的奶牛。因此，奶牛 1 到 6 的最大分数是奶牛 6 的分数：5。由于奶牛 7 的分数是 7，奶牛 7 是第一头分数大于奶牛 1 到 6 的奶牛。因此，第二条陈述“奶牛 9 是第一头分数大于奶牛 1 到 6 的奶牛”不可能为真。

评分： 输入 3 满足 $N \leq 10$ 且 $Q, C \leq 4$。 输入 4-8 满足 $N \leq 1000$。 输入 9-12 不满足任何额外限制。

题目致谢：Suhas Nagar

标签: USACO|2024|Silver

来源

USACO|2024|Silver