Đường Thẳng Tối Thiểu

Buổi 37 — Convex Hull Trick
Points
12
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ hàm số bậc nhất có dạng $y = a_i x + b_i$ ($1 \le i \le N$).

Bạn cần trả lời $Q$ truy vấn, mỗi truy vấn cho một số nguyên $x_j$ và yêu cầu tìm giá trị nhỏ nhất của $a_i x_j + b_i$ trên tất cả $N$ đường thẳng.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i, b_i$ ($|a_i| \le 10^6, |b_i| \le 10^{12}$).
  • Dòng cuối cùng chứa $Q$ số nguyên $x_1, x_2, \dots, x_Q$ ($|x_j| \le 10^6$).
Dữ liệu ra
  • Gồm $Q$ dòng, dòng thứ $j$ là giá trị nhỏ nhất tìm được tại $x_j$.
Ví dụ
Input Output
3 3
1 2
-1 4
0 3
0 1 5
2
3
-1
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $|a_i|, |x_j| \le 10^6$, $|b_i| \le 10^{12}$
Draft saved