Overview

This problem involves efficiently processing operations on \(N\) glasses arranged in a row: pouring champagne (overflow flows to the next level below) and querying the amount of champagne at a specified level.

Analysis

Problems with the Naive Approach

In the naive approach, each time champagne is poured, we process overflow sequentially starting from level 1. In the worst case, a single pour operation scans all \(N\) levels, resulting in \(O(NQ)\) total processing across \(Q\) operations. When \(N = Q = 2 \times 10^5\), this amounts to \(4 \times 10^{10}\) operations, causing TLE.

Key Insight: Once a Glass is Full, It Never Becomes Unfull

In this problem, there are only pouring operations — there is no operation to remove champagne from a glass. This means:

• The amount of champagne in each glass is monotonically non-decreasing
• Once a glass becomes full (reaches \(C_i\)), it remains full forever

This property eliminates the need to reprocess full glasses multiple times.

Solution: Frontier Pointer

We maintain a pointer front that points to “the first glass that is not yet full.”

• All glasses before front are completely full (exactly at capacity \(C_i\))
• When champagne is poured, it passes through full glasses and directly reaches the front-th glass

Concrete Example: When \(C = [3, 5, 2, 4]\)

1. Initially front = 0, pour \(V = 10\) → 10 enters glass[0] → exceeds capacity 3, 7 overflows → glass[0] = 3 (full), glass[1] += 7 → glass[1] = 7 > 5, 2 overflows → glass[1] = 5 (full), glass[2] += 2 → glass[2] = 2 ≤ 2 (exactly full) → front = 3
2. Next pour \(V = 1\) → since front = 3, glass[3] += 1 → glass[3] = 1 ≤ 4 → no overflow

Algorithm

1. Initialize front = 0 (index of the first non-full glass)
2. For operation 1 (pour):
   • If front >= N, all glasses are full and the champagne is lost
   • Otherwise, glass[front] += V
   • Process cascade from the front position downward until overflow stops
   • Advance front by the number of glasses that newly became full
3. For operation 2 (query):
   • Output the value of glass[k-1]

Key Point: Each glass undergoes the “becoming full” process at most once, so the total number of cascade processing steps across all operations is at most \(N\).

Complexity

• Time complexity: \(O(N + Q)\)
  • Cascade processing is \(O(N)\) total across all operations (each glass becomes full at most once: amortized analysis)
  • Reading and outputting each query is \(O(1)\)
• Space complexity: \(O(N)\) (array to store the state of glasses)

Implementation Notes

• The front pointer enables \(O(1)\) skipping of full glasses

• Don’t forget the boundary check i + 1 < N inside the cascade while loop (champagne that overflows from the bottom level is lost)

• Perform output in bulk (using sys.stdout.write for combined output) to reduce output overhead in Python

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    
    # glass[i] = current amount in glass i
    glass = [0] * N
    
    # We need to efficiently handle pouring.
    # Key insight: when we pour V into glass 0, overflow cascades down.
    # Naive simulation: pour into glass[0], then for each glass from top to bottom,
    # if glass[i] > C[i], overflow = glass[i] - C[i], glass[i] = C[i], glass[i+1] += overflow.
    # 
    # Worst case: Q pours each cascading through N glasses = O(NQ) which is 4*10^10 -- too slow.
    #
    # Optimization: track a "frontier" pointer. Once a glass is full, it stays full until...
    # Actually, glasses only get more champagne (never less), so once a glass is full it stays full.
    # 
    # We can maintain a pointer `front` = the first glass that is NOT full.
    # All glasses before `front` are full (glass[i] == C[i]).
    # When we pour V into glass 0:
    #   - Since glasses 0..front-1 are all full, the V ml will cascade through all of them
    #     and arrive at glass[front] (adding to whatever is there).
    #   - Then we need to check if glass[front] overflows, and cascade from there.
    #
    # So effectively: glass[front] += V, then cascade from front onwards.
    # The cascade from front will fill some glasses and stop.
    # Each glass can become full at most once across all operations, so total cascade steps = O(N) amortized.
    
    front = 0  # index of first non-full glass (or N if all full)
    
    out = []
    
    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            V = int(line[1])
            if front >= N:
                # All glasses are full, champagne is lost
                continue
            glass[front] += V
            # Cascade from front
            i = front
            while i < N and glass[i] > C[i]:
                overflow = glass[i] - C[i]
                glass[i] = C[i]
                if i + 1 < N:
                    glass[i + 1] += overflow
                # glass[i] is now full, so if i == front, advance front
                i += 1
            # Update front: all glasses from old front to i-1 are now full
            # front should be the first non-full glass
            # Since glasses before old front were already full, and we just filled front..i-1,
            # new front = i (if i < N and glass[i] <= C[i], then i is not full)
            # But we need to be careful: front was the first non-full, we filled some from front onwards
            if front < i:
                front = i  # i is either N, or glass[i] <= C[i]
        else:
            k = int(line[1]) - 1
            out.append(str(glass[k]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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