Elearning CodePath – CTP Online Judge

SƠN ĐƯỜNG

SONDUONG

## Đề bài

Một con đường được biểu diễn bởi đoạn thẳng từ $0$ đến $10^9$ trên trục số.

Có $n$ người thợ sơn, người thứ $i$ sơn đoạn $[L_i, R_i]$ trên con đường.

Hãy xác định:

- Tổng chiều dài của phần con đường được sơn ít nhất một lớp
- Chiều dài lớn nhất của một đoạn đường được sơn liên tục sau khi hợp nhất các đoạn sơn chồng lấn hoặc tiếp xúc nhau

## Dữ liệu vào

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

| Dòng | Nội dung |
|---|---|
| Dòng 1 | Chứa số nguyên dương $n$ |
| $n$ dòng tiếp theo | Dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ mô tả đoạn sơn của người thợ thứ $i$ |

## Dữ liệu ra

Ghi ra file `PAINTING.OUT` hai số nguyên:

- Số thứ nhất là tổng chiều dài con đường được sơn ít nhất một lớp
- Số thứ hai là chiều dài lớn nhất của một đoạn đường được sơn liên tục sau khi hợp nhất các đoạn

## Giới hạn

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

## Quy ước

Hai đoạn $[a,b]$ và $[b,c]$ được xem là nối liền nhau thành một đoạn sơn liên tục.

## Subtask

| Subtask | Điều kiện | Điểm |
|---|---|---|
| 1 | $n \le 1000$ | 30\% |
| 2 | $n \le 10^5$ | 70\% |

## Ví dụ

### Input
5
1 5
2 6
8 10
10 15
20 22

### Output

```text
14 7
```

## Giải thích

Sau khi hợp nhất các đoạn, ta thu được:

* $[1,6]$
* $[8,15]$
* $[20,22]$

Tổng chiều dài được sơn là:

$(6 - 1) + (15 - 8) + (22 - 20) = 5 + 7 + 2 = 14$

Chiều dài lớn nhất của một đoạn được sơn liên tục là:

$\max(5, 7, 2) = 7$

✅ Đã AC: 4 / 7 submissions