¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#6216
Subtarea

늑대 대장 2s 1024MB

Problemas

정올이는 그의 늑대들에게 새로운 무리 대장을 골라 주려고 한다. 이를 위해 그는 늑대 N ( 2 \leq N \leq 10^5) 마리와 인터뷰를 진행했으며, 각각의 후보에게 리더십 능력에 기반한 능력 점수인 정수 c_i를 부여했다. 각 점수는 1에서 C 사이의 값이며, 1 \leq C \leq 10^9이다.

하지만 많은 늑대를 인터뷰했기 때문에, 정올이는 모든 늑대의 점수를 기억하지는 못하고 있다. 그러나 그는 Q ( 1 \leq Q < N) 개의 숫자 쌍 (a_j, h_j)을 기억하는데, 이는 1번 늑대부터 a_j번 늑대까지의 모든 늑대보다 더 높은 능력 점수를 가진 첫 번째 위치하는 늑대가 h_j번 늑대라는 뜻이다 (즉, 1 \leq a_j < h_j \leq N).

정올이는 노트에 능력 점수 c_1, \dots, c_N (여기서 c_i = 0이면 늑대 i의 능력 점수를 잊어버렸음을 의미)과 Q개의 쌍 (a_j, h_j)을 적어놨다. 이 정보를 바탕으로 사전순으로 가장 작은 일관된 능력 점수 열을 구하거나, 그런 열이 존재하지 않는다는 것을 밝히자 (점수 열이 사전순으로 더 작으려면, 열이 서로 다른 첫 번째 늑대의 점수가 더 작아야 한다).


Entrada

첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스는 다음과 같이 구성된다:

첫 줄에 N, Q, C가 주어진다.

다음 줄에 점수 열 c_1, \dots, c_N (0 \leq c_i \leq C)이 주어진다.

마지막으로 Q 개의 줄에는 각각 쌍 (a_j, h_j)이 주어진다. 각 테스트 케이스 내에서 모든 a_j는 서로 다르다.

  • 각 입력은 T (1 \leq T \leq 20) 개의 독립적인 테스트 케이스를 포함한다.

  • 모든 테스트 케이스의 N 합은 최대 3 \cdot 10^5을 넘지 않는다.


Salida

각 테스트 케이스에 대해, 정올이가 기억하는 정보와 일관된 사전순으로 가장 작은 능력 점수 열을 출력하거나, 가능한 수열이 없다면 -1을 출력한다.


Subtarea

# Puntaje Condición
#120

N\le10; Q,C \le 4

#240

N\le 1000

#340

추가 제약 조건 없음


Ejemplo #1

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

  • (3,5): max(c_1, c_2, c_3)보다 처음으로 높은 점수를 가진 늑대가 5번 위치에 있다는 의미.

  • (1,5): c_1보다 처음으로 높은 점수를 가진 늑대가 5번 위치에 있다는 의미.

  • (4,5): max(c_1, c_2, c_3, c_4)보다 처음으로 높은 점수를 가진 늑대가 5번 위치에 있다는 의미.

위 조건들을 만족시키는 사전순으로 가장 빠른 수열은 4, 2, 1, 4, 5 이다.


Ejemplo #2

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


Fuente

USACO 2024 January Silver

Debes iniciar sesión para escribir código.