Giải đấu hiệp sĩ

Điểm: 4,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Có $n$ hiệp sĩ tham gia một giải đấu, được đánh số từ $1$ đến $n$ . Giải đấu diễn ra qua $m$ trận đấu liên tiếp. Trong trận thứ $i$ , tất cả những hiệp sĩ còn lại có số hiệu trong đoạn $[l_{i}, r_{i}]$ tham gia thi đấu. Sau trận, chỉ duy nhất hiệp sĩ số $x_{i}$ chiến thắng và tiếp tục giải; mọi hiệp sĩ còn lại trong đoạn $[l_{i}, r_{i}]$ bị loại.

Người chiến thắng của trận cuối cùng ( $x_{m}$ ) là nhà vô địch của giải đấu.

Ta nói hiệp sĩ $a$ đánh bại hiệp sĩ $b$ nếu cả hai cùng tham gia một trận đấu và $a$ là người thắng trận đó. Với mỗi hiệp sĩ, hãy xác định ai là người đã đánh bại mình.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l_{i}$ , $r_{i}$ , $x_{i}$ — mô tả một trận đấu.

Dữ liệu đảm bảo hợp lệ và phù hợp với mô tả: tại mỗi trận luôn có ít nhất hai hiệp sĩ còn lại trong đoạn $[l_{i}, r_{i}]$ , và $x_{i}$ là một trong số đó.

Dữ liệu ra

In ra $n$ số nguyên trên cùng một dòng. Số thứ $i$ là số hiệu hiệp sĩ đã đánh bại hiệp sĩ $i$ . Nếu hiệp sĩ $i$ là nhà vô địch (không thua trận nào), in ra $0$ .

Ràng buộc

$2 \leq n \leq 3 \cdot 10^{5}$
$1 \leq m \leq 3 \cdot 10^{5}$
$1 \leq l_{i} < r_{i} \leq n$
$l_{i} \leq x_{i} \leq r_{i}$

Ví dụ

Input	Output	Giải thích
4 3 1 2 1 1 3 3 1 4 4	3 1 4 0	Trận 1: hiệp sĩ 1 và 2 đấu, 1 thắng — 2 bị 1 đánh bại. Trận 2: 1 và 3 đấu, 3 thắng — 1 bị 3 đánh bại. Trận 3: 3 và 4 đấu, 4 thắng — 3 bị 4 đánh bại. Hiệp sĩ 4 vô địch.
8 4 3 5 4 3 7 6 2 8 8 1 8 1	0 8 4 6 4 8 6 1	Trận 1 loại 3 và 5 (đều thua 4). Trận 2 đưa 4, 6, 7 vào đấu — 4 và 7 bị 6 đánh bại. Trận 3: 2, 6, 8 đấu, 8 thắng. Trận 4: 1 và 8 đấu, 1 thắng và là nhà vô địch.

Bình luận

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