Điểm Cao Nhất Trên Trục

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

Ban đầu tập các đường thẳng là rỗng. Bạn cần xử lý $Q$ truy vấn thuộc một trong hai loại:

  • 1 a b: Thêm đường thẳng $y = ax + b$ vào tập hợp.
  • 2 x: Tìm giá trị lớn nhất của $ax + b$ trong tất cả các đường thẳng hiện có tại hoành độ $x$. (Đảm bảo có ít nhất một đường thẳ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 mô tả một truy vấn theo định dạng trên.
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tìm được.
Ví dụ
Input Output
6
1 2 1
1 -1 5
2 0
2 3
1 10 -20
2 5
5
7
30
Giới hạn
  • $1 \le Q \le 10^5$
  • $|a|, |x| \le 10^6$, $|b| \le 10^{12}$
Draft saved