Chiếc Bể Đầy Đầu Tiên
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Có N bể chứa xếp thành hàng, bể i đang chứa a_i lít nước. Người ta đổ thêm x lít vào mọi bể trong một đoạn (x có thể âm nếu rút bớt). Với mỗi câu hỏi, cho ngưỡng v, hãy tìm bể đầu tiên từ trái sang có lượng nước ít nhất v lít.
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một thao tác:
1 l r x: cộng x vào a_l..a_r.2 v: hỏi chỉ số nhỏ nhất i sao cho a_i ≥ v.
Dữ liệu ra
Với mỗi thao tác loại 2, in ra chỉ số i nhỏ nhất thỏa mãn, hoặc -1 nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n-4 7 -7 -6 -3\n2 8\n1 4 5 -7\n1 5 5 1\n2 -7 | -1\n1 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- |a_i|, |x|, |v| ≤ 10^9
Community Discussion