Elearning CodePath – CTP Online Judge

KIỂM TRA PHỦ

KIEMTRAPHU

## Đề bài

Cho một đoạn thẳng $[A, B]$ trên trục số và $n$ đoạn thẳng nhỏ $[L_i, R_i]$.

Hãy kiểm tra xem hợp của $n$ đoạn thẳng nhỏ đã cho có phủ kín hoàn toàn đoạn $[A, B]$ hay không.

Lưu ý rằng chỉ cần còn hở một phần rất nhỏ của đoạn $[A, B]$ thì cũng được xem là chưa phủ kín.

## Dữ liệu vào

Dữ liệu vào từ file `KIEMTRAPHU.INP`.

| Dòng | Nội dung |
|---|---|
| Dòng 1 | Chứa ba số nguyên $n, A, B$ |
| $n$ dòng tiếp theo | Dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ mô tả đoạn nhỏ thứ $i$ |

## Dữ liệu ra

Ghi ra file `KIEMTRAPHU.OUT`.

| Giá trị in ra | Ý nghĩa |
|---|---|
| `YES` | Nếu các đoạn nhỏ phủ kín hoàn toàn đoạn $[A, B]$ |
| `NO` | Nếu các đoạn nhỏ không phủ kín hoàn toàn đoạn $[A, B]$ |

## Giới hạn

| Thành phần | Ràng buộc |
|---|---|
| $1 \le n \le 2 \times 10^5$ |
| $0 \le A < B \le 10^9$ |
| $0 \le L_i \le R_i \le 10^9$ |

## Quy ước

Mỗi đoạn đều là đoạn đóng. Hai đoạn $[x, y]$ và $[y, z]$ được xem là phủ liên tục, không có khoảng hở.

## Subtask

| Subtask | Điều kiện | Điểm |
|---|---|---|
| 1 | $n \le 20$ | 20\% |
| 2 | $n \le 2000$ | 30\% |
| 3 | Không có ràng buộc gì thêm | 50\% |

## Ví dụ 1

### Input
3 2 10
1 4
4 7
7 12

### Output
YES

## Ví dụ 2

### Input
3 2 10
1 4
5 7
7 12

### Output
NO

### Giải thích

Ở ví dụ 1, các đoạn nhỏ phủ liên tục từ $2$ đến $10$.

Ở ví dụ 2, giữa $4$ và $5$ còn khoảng hở nên đoạn $[2,10]$ chưa được phủ kín.

✅ Đã AC: 5 / 19 submissions