Quá nhiều đoạn

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.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

Cho $n$ đoạn thẳng trên trục số $O X$ . Các đoạn có thể giao nhau, lồng nhau hoặc trùng nhau. Đoạn thứ $i$ là $[l_{i}; r_{i}]$ (với $l_{i} \leq r_{i}$ ) và phủ tất cả các điểm nguyên $j$ thoả $l_{i} \leq j \leq r_{i}$ .

Một điểm nguyên được gọi là điểm xấu nếu nó bị phủ bởi nhiều hơn $k$ đoạn.

Hãy xoá đi số lượng đoạn ít nhất sao cho sau khi xoá, không còn điểm xấu nào trên trục số.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ .
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_{i}$ và $r_{i}$ — hai đầu mút của đoạn thứ $i$ .

Dữ liệu ra

Dòng đầu in một số nguyên $m$ — số đoạn ít nhất cần xoá.
Dòng thứ hai in $m$ số nguyên phân biệt $p_{1}, p_{2}, \dots, p_{m}$ — chỉ số của các đoạn bị xoá (theo thứ tự tuỳ ý).

Nếu có nhiều đáp án, in ra bất kỳ.

Ràng buộc

$1 \leq k \leq n \leq 2 \cdot 10^{5}$
$1 \leq l_{i} \leq r_{i} \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
7 2 11 11 9 11 7 8 8 9 7 8 9 11 7 9	3 7 4 1	Xoá $3$ đoạn (một phương án là chỉ số $7, 4, 1$ ). Sau đó mỗi điểm nguyên bị phủ tối đa $2$ lần. Đáp án không duy nhất.
5 1 29 30 30 30 29 29 28 30 30 30	3 1 4 2	$k = 1$ nên mỗi điểm chỉ được phủ bởi đúng $1$ đoạn. Cần xoá ít nhất $3$ đoạn.
6 1 2 3 3 3 2 3 2 2 2 3 2 3	4 1 3 5 6	Sau khi xoá $4$ đoạn, các đoạn còn lại không chồng lên nhau quá $1$ lần tại bất kỳ điểm nguyên nào.

Bình luận

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