Máy Phóng

Đ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

Trên một con đường thẳng (trục số), có $N$ máy phóng và $M$ truy vấn vận chuyển. Mỗi máy phóng $i$ có thể phóng hàng từ vị trí $x_{i}$ đến vị trí $y_{i}$ trong thời gian $t_{i}$ . Mỗi truy vấn $j$ yêu cầu vận chuyển hàng từ vị trí $a_{j}$ đến vị trí $b_{j}$ .

Để vận chuyển hàng từ $a_{j}$ đến $b_{j}$ , có hai lựa chọn:

Không dùng máy phóng: mất $| a_{j} - b_{j} |$ đơn vị thời gian.
Dùng máy phóng $i$ : đi bộ từ $a_{j}$ đến $x_{i}$ , phóng đến $y_{i}$ , rồi đi bộ đến $b_{j}$ ; tổng thời gian là $| a_{j} - x_{i} | + t_{i} + | y_{i} - b_{j} |$ .

Với mỗi truy vấn, hãy tìm thời gian vận chuyển nhỏ nhất (có thể dùng tối đa một máy phóng).

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $x_{i}$ , $y_{i}$ , $t_{i}$ mô tả máy phóng $i$ .
$M$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a_{j}$ , $b_{j}$ mô tả truy vấn $j$ .

Dữ liệu ra

In ra $M$ dòng, dòng thứ $j$ là thời gian vận chuyển nhỏ nhất cho truy vấn $j$ .

Ràng buộc

$1 \leq N, M \leq 10^{5}$
$0 \leq x_{i}, y_{i}, t_{i} \leq 10^{9}$
$0 \leq a_{j}, b_{j} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
2 3 0 10 1 13 8 2 1 12 5 2 20 7	4 3 10	Truy vấn 1 (1→12): dùng máy 1 tốn \|1-0\|+1+\|10-12\|=4. Truy vấn 2 (5→2): đi thẳng \|5-2\|=3. Truy vấn 3 (20→7): dùng máy 2 tốn \|20-13\|+2+\|8-7\|=10.

Ghi chú

Bài toán yêu cầu xử lý nhanh $M$ truy vấn với $N$ máy phóng; thuật toán $O (N M)$ sẽ không đủ nhanh.

Bình luận

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