Overview

This is a simulation problem where you pour water into \(N\) flowerpots in order from the smallest-numbered pot, filling up the remaining capacity of each pot.

Analysis

Since the procedure of operations is clearly defined in this problem, you can obtain the correct answer by faithfully reproducing (simulating) that procedure as-is.

Key observations: - The remaining capacity of each flowerpot \(i\) can be calculated as \(C_i - S_i\). - If the remaining water is greater than or equal to the remaining capacity, fill that flowerpot to full and reduce the remaining water accordingly. - If the remaining water is less than the remaining capacity, pour all the remaining water into that pot, and nothing is added to subsequent flowerpots.

Concrete example:

Consider the case where \(N = 3, M = 5\) with the following flowerpots:

Flowerpot	Capacity \(C_i\)	Current \(S_i\)	Remaining capacity \(C_i - S_i\)
1	6	3	3
2	4	2	2
3	5	1	4

• Flowerpot 1: remaining capacity \(3\), remaining water \(5 \geq 3\) → full (\(6\) liters), remaining water \(5 - 3 = 2\)
• Flowerpot 2: remaining capacity \(2\), remaining water \(2 \geq 2\) → full (\(4\) liters), remaining water \(2 - 2 = 0\)
• Flowerpot 3: remaining capacity \(4\), remaining water \(0 < 4\) → stays at \(1 + 0 = 1\) liters

The answer is \(6, 4, 1\).

Comparison with a naive approach:

In this problem, if you simulate pouring one liter at a time, it will result in TLE since \(M\) can be up to \(10^{18}\). However, by “pouring the entire remaining capacity at once” for each flowerpot, the loop only runs \(N\) times.

Algorithm

1. Initialize the remaining water remaining to \(M\).
2. For each flowerpot \(i = 1, 2, \ldots, N\) in order, do the following:
   • Calculate the remaining capacity \(\text{space} = C_i - S_i\).
   • If \(\text{remaining} \geq \text{space}\), set the water amount of flowerpot \(i\) to \(C_i\) (full), and subtract \(\text{space}\) from \(\text{remaining}\).
   • If \(\text{remaining} < \text{space}\), set the water amount of flowerpot \(i\) to \(S_i + \text{remaining}\), and set \(\text{remaining} = 0\).
3. Output the final water amount of each flowerpot.

Complexity

• Time complexity: \(O(N)\) — each flowerpot is examined only once
• Space complexity: \(O(N)\) — for storing the input and results

Implementation Notes

• Since \(M\) can be as large as \(10^{18}\), you need to use long long in C++ and similar languages. In Python, there is no need to worry about integer overflow.

• Since the input can be up to \(2 \times 10^5\) lines, reading all input at once with sys.stdin.buffer.read() speeds up the input processing.

• Output is also done all at once using '\n'.join(...) for faster output.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = []
    S = []
    for i in range(N):
        c = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        C.append(c)
        S.append(s)
    
    result = []
    remaining = M
    for i in range(N):
        space = C[i] - S[i]
        if remaining >= space:
            result.append(C[i])
            remaining -= space
        else:
            result.append(S[i] + remaining)
            remaining = 0
    
    sys.stdout.write('\n'.join(map(str, result)) + '\n')

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.6opus-thinking.