[VTT Q4 Contest 03] Bài 4: Phủ đoạn thẳng [COVER]

Xem dạng PDF

Gửi bài giải


Điểm: 4,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: COVER.INP
Output: COVER.OUT

Dạng bài
Ngôn ngữ cho phép
C++, Pascal, PyPy, Python

Trên trục số ~Ox~ có ~n~ đoạn thẳng, đoạn thứ ~i~ có hai đầu mút là ~l_i~ và ~r_i~. Hãy chọn ra ít đoạn nhất trong số đó sao cho chúng phủ kín toàn bộ đoạn ~[a, b]~.

Dữ liệu

  • Dòng đầu tiên chứa ba số nguyên dương ~n, a, b~ (~1 \le n \le 10^5~, ~1 \le a \le b \le 10^5~) lần lượt là số đoạn và hai đầu mút của đoạn cần phủ.
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le 10^5~).

Kết quả

  • Dòng đầu tiên ghi số nguyên ~k~ là số đoạn được chọn. Nếu không có cách chọn nào phủ được thì ghi ~-1~.
  • Nếu có cách chọn, ghi tiếp ~k~ dòng, mỗi dòng một số nguyên là chỉ số (thứ tự trong input) của một đoạn được chọn.

Ví dụ

Ví dụ 1

COVER.INP

8 2 10
4 8
1 3
2 3
1 4
3 4
7 10
9 11
8 11

COVER.OUT

3
1
4
6
Ví dụ 2

COVER.INP

4 1 200
1 4
2 5
4 5
6 45

COVER.OUT

-1

Bình luận

Hãy đọc nội quy trước khi bình luận.


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