Lộ Trình Moo II

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 du lịch qua các sân bay sử dụng các chuyến bay có thể du hành thời gian. Cô bắt đầu tại sân bay 1 vào thời điểm 0 và cần tìm thời điểm đến sớm nhất tại mỗi sân bay.

Mỗi chuyến bay $j$ xuất phát từ sân bay $c_{j}$ lúc $r_{j}$ , đến sân bay $d_{j}$ lúc $s_{j}$ . Du hành thời gian có thể xảy ra ( $s_{j} < r_{j}$ được phép). Tại mỗi sân bay $i$ , có thời gian chờ nối chuyến $a_{i}$ : để lên chuyến bay khởi hành lúc $r$ từ sân bay $i$ , Bessie phải đến sân bay $i$ không muộn hơn thời điểm $r - a_{i}$ .

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$ ( $1 \leq N, M \leq 2 \cdot 10^{5}$ ) — số sân bay và số chuyến bay.
$M$ dòng tiếp theo: Bốn số nguyên $c_{j}$ , $r_{j}$ , $d_{j}$ , $s_{j}$ — sân bay đi, thời gian đi, sân bay đến, thời gian đến.
Dòng cuối: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ — thời gian chờ nối chuyến tại mỗi sân bay.

Dữ liệu ra

$N$ dòng, mỗi dòng chứa thời điểm đến sớm nhất tại sân bay $i$ , hoặc $- 1$ nếu không thể đến được.

Ràng buộc

$1 \leq N, M \leq 2 \cdot 10^{5}$
$0 \leq r_{j}, s_{j} \leq 10^{9}$
$0 \leq a_{i} \leq 10^{9}$
Giới hạn thời gian: 4 giây

Ví dụ

Input	Output	Giải thích
3 3 1 0 2 10 2 11 2 0 2 1 3 20 10 1 10	0 0 20	Từ sân bay 1 bay đến 2 lúc t=10. Chờ 1 giây, lên chuyến bay lúc t=11 quay về t=0. Rồi từ t=0 chờ 1 giây, lên chuyến bay lúc t=1 đến sân bay 3 lúc t=20.
3 3 1 0 2 10 2 10 2 0 2 1 3 20 10 1 10	0 10 -1	Chuyến bay thứ 2 khởi hành lúc t=10 nhưng Bessie đến sân bay 2 lúc t=10, cần chờ 1 giây nên không kịp (cần đến trước t=9). Sân bay 3 không thể đến.

Bình luận

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