Nén Tọa Độ Đỉnh Lồi

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

Xử lý $Q$ truy vấn trên một tập các đường thẳng (ban đầu rỗng) với hoành độ rất lớn ($|x| \le 10^9$):

  • 1 a b: Thêm đường thẳng $y = ax + b$ vào tập hợp.
  • 2 x: Tìm giá trị nhỏ nhất của $ax + b$ tại $x$ trong số các đường thẳng đã thêm (đảm bảo tập hợp không rỗng khi truy vấn loại 2 xuất hiện).
Dữ liệu vào
  • Dòng đầu chứa số nguyên $Q$ ($1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng là một truy vấn loại 1 hoặc 2.
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.
Ví dụ
Input Output
6
1 2 -1000000000
1 -3 500000000
2 1000000000
2 -1000000000
1 0 -100
2 0
-2500000000
-3000000000
-1000000000
Giới hạn
  • $1 \le Q \le 10^5$
  • $|a| \le 10^6$, $|b| \le 10^{12}$, $|x| \le 10^9$
Draft saved