Năng Lực Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác John phỏng vấn $N$ con bò và cho mỗi con một điểm "năng lực" từ $1$ đến $C$ . Bác nhớ $Q$ cặp $(a_{j}, h_{j})$ : con bò thứ $h_{j}$ là con bò đầu tiên có điểm năng lực lớn hơn nghiêm ngặt tất cả các con bò từ $1$ đến $a_{j}$ .

Cho một dãy điểm năng lực, trong đó một số giá trị đã biết và các giá trị còn lại là $0$ (chưa biết). Hãy tìm dãy nhỏ nhất theo thứ tự từ điển thỏa mãn tất cả các ràng buộc, hoặc trả về $- 1$ nếu không tồn tại.

Dữ liệu vào

Dòng đầu tiên: số nguyên $T$ ( $1 \leq T \leq 20$ ) - số test case.
Mỗi test case:
- Dòng 1: ba số nguyên $N$ , $Q$ , $C$ ( $2 \leq N \leq 10^{5}$ , $1 \leq Q < N$ , $1 \leq C \leq 10^{9}$ ).
- Dòng 2: $N$ số nguyên $c_{1}, \dots, c_{N}$ ( $0 \leq c_{i} \leq C$ ), với $0$ là chưa biết.
- $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a_{j}$ và $h_{j}$ ( $1 \leq a_{j} < h_{j} \leq N$ ).

Dữ liệu ra

Với mỗi test case, in dãy nhỏ nhất theo thứ tự từ điển thỏa mãn ràng buộc, hoặc -1.

Ràng buộc

$1 \leq T \leq 20$
$2 \leq N \leq 10^{5}$
$1 \leq C \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
1 7 3 5 1 0 2 3 0 4 0 1 2 3 4 4 5	1 2 2 3 4 4 1	Dãy nhỏ nhất theo thứ tự từ điển thỏa mãn 3 ràng buộc.

Bình luận

Không có bình luận tại thời điểm này.