Overview

This is a simulation problem where you pour \(M\) liters of prepared water into \(N\) flowerpots sequentially from the first one. When filling each flowerpot without exceeding its capacity, determine how many liters of water are in each flowerpot at the end.

Analysis

The key point of this problem is to sequentially determine which is smaller: “the water you currently have” or “the remaining capacity of the flowerpot”.

1. Calculating remaining capacity: The maximum capacity of the \(i\)-th flowerpot is \(C_i\) and the current amount of water is \(S_i\), so it can hold \(C_i - S_i\) more liters of water.
2. Determining the amount of water to pour:
   • If the remaining water \(M\) is greater than the remaining capacity, fill the remaining capacity completely.
   • If the remaining water \(M\) is less than the remaining capacity, pour all the water \(M\) you have into that flowerpot.
   • Mathematically, this can be expressed as \(\min(M, C_i - S_i)\).
3. Updating the remaining water: The amount of water on hand \(M\) decreases by the amount poured. Once the water reaches \(0\), no more water can be added to subsequent flowerpots.

Looking at the constraints, \(N\) can be as large as \(2 \times 10^5\), so we need an \(O(N)\) algorithm that performs one calculation per flowerpot. Also, since \(M\) can reach up to \(10^{18}\), we need to handle large numbers (64-bit integers) (Python handles this natively).

Algorithm

The simulation is performed with the following steps:

1. Read \(N\) and \(M\) from input.
2. Repeat the following operations in order for \(i = 1, 2, \dots, N\):
   • Calculate the remaining capacity of the \(i\)-th flowerpot: empty_space \(= C_i - S_i\).
   • Calculate the actual amount of water to pour: water_to_add \(= \min(M, \text{empty\_space})\).
   • Record the final amount of water: \(S_i + \text{water\_to\_add}\).
   • Update the amount of water on hand: \(M = M - \text{water\_to\_add}\).
3. Output the final amount of water in all flowerpots.

Complexity

• Time complexity: \(O(N)\)
  • Processing completes in a single loop over the \(N\) flowerpots, making it very fast.
• Space complexity: \(O(N)\)
  • Memory is needed for the array holding the results and for storing the input data.

Implementation Notes

• Fast I/O: Since \(N\) is large, repeatedly calling input() in Python may result in a Time Limit Exceeded (TLE). You can speed things up by reading all input at once with sys.stdin.read().split() and outputting everything together at the end with sys.stdout.write.

• Incremental updates: By updating \(M\) within the loop, you always correctly track “the amount of water currently available.” Once the water reaches \(0\), min(0, empty_space) becomes \(0\), so the behavior of “not adding any water” occurs naturally.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 植木鉢の数, M: 用意した水の量
    N = int(input_data[0])
    M = int(input_data[1])
    
    results = []
    # 植木鉢の情報を順番に処理する
    # 2番目のインデックスから開始し、2つずつ読み取る (C_i, S_i)
    for i in range(N):
        C_i = int(input_data[2 + 2 * i])
        S_i = int(input_data[3 + 2 * i])
        
        # この植木鉢に入れられる水の最大量
        empty_space = C_i - S_i
        
        # 実際に注ぐ水の量 (残り容量と所持している水の量の小さい方)
        water_to_add = min(M, empty_space)
        
        # 操作後の水の量を計算
        final_water = S_i + water_to_add
        results.append(str(final_water))
        
        # 残りの水の量を更新
        M -= water_to_add
        
    # 結果をまとめて出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.