Đường Thẳng Tối Thiểu
Points
12
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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}$
Community Discussion