Giải Đấu Động Học
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ hàm bậc nhất $y_i(t) = a_i t + b_i$ ($1 \le i \le N$). Bạn cần xử lý $Q$ truy vấn thuộc hai loại:
1 i a b: Cập nhật hàm thứ $i$ thành $y_i(t) = a t + b$.2 t: Tìm giá trị nhỏ nhất $\min_{1 \le i \le N} y_i(t)$ tại thời điểm $t$.
Biết rằng các giá trị $t$ trong truy vấn loại 2 xuất hiện theo thứ tự không giảm.
Dữ liệu vào
- Dòng đầu 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$ ban đầu.
- $Q$ dòng cuối, mỗi dòng mô tả 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 |
|---|---|
| 3 5 5 0 2 10 -1 30 2 0 2 5 1 1 -3 20 2 5 2 10 |
0 20 5 -10 |
Giới hạn
- $1 \le N, Q \le 10^5$
- $|a_i|, |t| \le 10^6$, $|b_i| \le 10^{12}$
Community Discussion