当前没有测试数据。

C. Racing

题目描述

在 2077 年，一项名为“爱好无人机”的运动在机器人中越来越受欢迎。

你已经拥有一架无人机，并且想要赢得比赛。为此，你的无人机需要穿越一个包含 n 个障碍物的赛道。

第 i 个障碍物由两个数字 l_i 和 r_i 定义。设你的无人机在第 i 个障碍物处的高度为 h_i，那么无人机通过该障碍物的条件是 l_i ≤ h_i ≤ r_i。初始时，无人机在地面上，即 h_0 = 0。

无人机的飞行程序由数组 d_1, d_2, ..., d_n 表示，其中 h_i - h_{i-1} = d_i，且 0 ≤ d_i ≤ 1。这意味着无人机在两个障碍物之间要么保持高度不变，要么升高 1。你已经有了一个飞行程序，但其中一些 d_i 是未知的，标记为 -1。请将未知的 d_i 替换为 0 或 1，以创建一个能让无人机穿越整个赛道的飞行程序；如果无法做到，请输出 -1。

输入格式

输入包含多组测试用例。第一行输入测试用例数 t（1 ≤ t ≤ 10^4）。每组测试用例的描述如下：

• 第一行输入一个整数 n（1 ≤ n ≤ 2×10^5），表示数组 d 的长度。
• 第二行输入 n 个整数 d_1, d_2, ..., d_n（-1 ≤ d_i ≤ 1），其中 d_i = -1 表示该位置的 d_i 未知。
• 接下来 n 行，每行输入两个整数 l_i 和 r_i（0 ≤ l_i ≤ r_i ≤ n），分别表示第 i 个障碍物的高度范围。

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

输出格式

对于每组测试用例，如果存在合法的飞行程序，输出 n 个整数（替换后的 d 数组）；否则输出 -1。

样例输入

5
4
0 -1 -1 1
0 4
1 2
2 4
1 4
3
0 -1 -1
0 1
2 2
0 3
2
-1 -1
0 0
2 2
8
-1 -1 1 -1 -1 0 0 -1
0 0
0 1
0 2
0 2
1 3
0 4
2 5
4 5
1
0
1 1

样例输出

0 1 1 1
-1
-1
0 1 1 0 1 0 0 1
-1

样例解释

样例 1

• 输入：n=4，d 数组为 [0,-1,-1,1]，4 个障碍物的范围分别为 [0,4]、[1,2]、[2,4]、[1,4]。
• 输出：[0,1,1,1]
• 解释：
  1. 初始高度 h0=0。
  2. d1=0 → h1 = h0 + 0 = 0，满足第 1 个障碍物的范围 [0,4]。
  3. d2=1 → h2 = h1 + 1 = 1，满足第 2 个障碍物的范围 [1,2]。
  4. d3=1 → h3 = h2 + 1 = 2，满足第 3 个障碍物的范围 [2,4]。
  5. d4=1 → h4 = h3 + 1 = 3，满足第 4 个障碍物的范围 [1,4]。 整个飞行过程的高度序列为 [0,0,1,2,3]，全部满足对应障碍物的要求，因此该方案合法。

样例 2

• 输入：n=3，d 数组为 [0,-1,-1]，3 个障碍物的范围分别为 [0,1]、[2,2]、[0,3]。
• 输出：-1
• 解释：
  1. 初始高度 h0=0。
  2. d1=0 → h1 = 0 + 0 = 0，满足第 1 个障碍物 [0,1]。
  3. 第 2 个障碍物要求 h2=2，但 h2 = h1 + d2 = 0 + d2。由于 d2 只能是 0 或 1，h2 最大为 1，无法达到 2，因此无解。

样例 3

• 输入：n=2，d 数组为 [-1,-1]，2 个障碍物的范围分别为 [0,0]、[2,2]。
• 输出：-1
• 解释：
  1. 初始高度 h0=0。
  2. 第 1 个障碍物要求 h1=0 → d1 必须为 0（因为 h1 = h0 + d1 = 0 + d1）。
  3. 第 2 个障碍物要求 h2=2 → h2 = h1 + d2 = 0 + d2。由于 d2 只能是 0 或 1，h2 最大为 1，无法达到 2，因此无解。

样例 4

• 输入：n=8，d 数组为 [-1,-1,1,-1,-1,0,0,-1]，8 个障碍物的范围依次为 [0,0]、[0,1]、[0,2]、[0,2]、[1,3]、[0,4]、[2,5]、[4,5]。
• 输出：[0,1,1,0,1,0,0,1]
• 解释： 高度序列计算如下： h0=0 → d1=0 → h1=0（满足 [0,0]） h1=0 → d2=1 → h2=1（满足 [0,1]） h2=1 → d3=1 → h3=2（满足 [0,2]） h3=2 → d4=0 → h4=2（满足 [0,2]） h4=2 → d5=1 → h5=3（满足 [1,3]） h5=3 → d6=0 → h6=3（满足 [0,4]） h6=3 → d7=0 → h7=3（满足 [2,5]） h7=3 → d8=1 → h8=4（满足 [4,5]） 所有高度均满足对应障碍物的范围，方案合法。

样例 5

• 输入：n=1，d 数组为 [0]，障碍物范围为 [1,1]。
• 输出：-1
• 解释： h0=0 → d1=0 → h1=0，不满足 [1,1]，因此无解。

提示

1. 关键约束：h_i 是前缀和（h_i = h_{i-1} + d_i），且 0 ≤ d_i ≤ 1，因此 h_i 是非递减序列，且 h_i ≤ i（因为最多每次升高 1，初始为 0）。
2. 对于每个位置 i，h_i 必须满足 l_i ≤ h_i ≤ r_i，同时 h_i ≥ h_{i-1}（因为 d_i ≥ 0）且 h_i ≤ h_{i-1} + 1（因为 d_i ≤ 1）。
3. 解题思路：可以通过贪心算法，从左到右确定每个 d_i 的值，同时维护 h_i 的可能范围，确保每个步骤都满足约束。如果某个步骤无法找到合法的 d_i，则输出 -1。