Taxi

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie lái taxi trên một con đường dài $M$ đơn vị (từ vị trí $0$ đến $M$ ). Có $N$ hành khách, hành khách $i$ muốn đi từ vị trí $s_{i}$ đến $t_{i}$ . Bessie xuất phát từ vị trí $0$ và phải kết thúc tại vị trí $M$ .

Bessie chỉ chở được 1 hành khách mỗi lúc.
Bessie có thể đặt hành khách xuống ở bất kỳ điểm nào (không nhất thiết phải tại điểm đến).
Tìm quãng đường lái tối thiểu để chở tất cả hành khách đến điểm đến.

Lưu ý: Đáp án có thể vượt quá giới hạn số nguyên 32-bit.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): Hai số nguyên $s_{i}$ và $t_{i}$

Dữ liệu ra

Một số nguyên duy nhất: tổng quãng đường tối thiểu

Ràng buộc

$1 \leq N \leq 100000$
$1 \leq M \leq 10^{9}$
$0 \leq s_{i}, t_{i} \leq M$

Ví dụ

Input	Output	Giải thích
2 10 0 9 6 5	12	Chở khách 2 từ 6→5, chở khách 1 từ 0→9. Tổng = 1 + 9 + đi không = 12.
10 10 1 2 6 1 8 5 2 7 1 2 5 3 10 10 5 1 4 9 10 2	54	Tối ưu hóa hành trình để tổng quãng đường = 54.

Bình luận

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