Subtask 1

• Ta có thể dựng lại mảng ~2D~ ~n\times m~ như trong đề bài rồi làm như đề yêu cầu với độ phức tạp ~O(n*m)~.

Subtask 2

• Ta thấy rằng ~a_i\le 10^5~ nên chắc chắn rằng nhiều nhất ~10^5~ bồn chứa sẽ được sử dụng đến. Vì thế, ta chỉ quan tâm nhiều nhất ~10^5~ bồn chứa. Nên nếu ~m>10^5~ thì ta có thể đặt ~m~ là ~10^5~ luôn.

• Nếu như ta làm thuật toán như Subtask 1 mà chỉ lưu mảng đáp án của ~m~ máy và cập nhật đáp án từ từ thì độ phức tạp sẽ là ~O(n*min(m,10^5))~ thì sẽ là khoảng ~10^8~ vừa đủ thời gian chạy. Trên thực tế, thời gian chạy sẽ thấp hơn rất nhiều.

Subtask 3

• Ta mặc định ~m\le 10^5~.

• Ta thấy rằng với giá trị ~a_i~ thì nó sẽ lắp đầy hết ~k_i~ bể đầu tiên. Vì thế, ta có thể đánh dấu là bể thứ ~i~ được lắp đầy bao nhiêu lần và được lặp không đầy một lượng nhiêu. Việc đánh dấu thứ hai có thể thực hiện trong ~O(1)~. Nhưng việc đánh dấu đầu tiên thì khó hơn.

• Ta xét bài toán con: Cho ~q~ lần truy vấn cập nhật đoạn ~[l,r]~ tăng lên giá trị ~c~ rồi cuối cùng xuất ra giá trị của tất cả các phần tử. Bài toán này có thể giải quyết trong độ phức tạp ~O(n+q)~ với ứng dụng của mảng hiệu. Vì thế, bước đánh dầu đầu ta có thể sử dụng mảng hiệu.

• Vấn đề cuối cùng là cách để tìm giá trị ~k_i~ với mỗi giá trị ~a_i~. Ta thấy, với ~a_i~ càng lớn thì ~k_i~ cũng sẽ càng lớn nên ta có thể sử dụng tìm kiếm nhị phân để tìm ~k_i~.

• Như vậy thuật toán của mình sẽ là với mỗi giá trị ~a_i~ thì ta sẽ sử dụng mảng hiệu để cập nhật ~k_i~ máy đầu tiên là bể được lắp đầy và cập nhật máy ~k_i+1~ được thêm một lượng nước thừa nào đó. Cuối cùng, ta sẽ sử dụng mảng hiệu và số lượng nước dư của mỗi máy để tính lượng nước mỗi máy xử lý. Độ phức tạp của thuật toán là ~O(n*\log(m)+m)~.