Overview

This problem involves simulating pouring champagne into a champagne tower consisting of \(N\) glasses arranged in series. When a glass becomes full, the overflow immediately flows down to the glass below.

A naive simulation would repeatedly scan through glasses that are already full, which would not meet the time limit. Instead, we use Union-Find (Disjoint Set Union) to efficiently find the “next glass with remaining capacity,” enabling an efficient simulation.

---

Analysis

Naive Approach (Simulation) and Its Limitations

Consider a straightforward method where, each time champagne is poured, we start from the 1st glass and repeat the process: “Is it full? If so, move to the next level.”

For example, suppose all glasses from level \(1\) to level \(N-1\) are already full. When a small amount of champagne is poured into the 1st glass, it passes through all glasses from level \(1\) to level \(N-1\) and ultimately reaches level \(N\). This requires \(N\) steps each time just for this determination.

Repeating such operations \(Q\) times results in a worst-case time complexity of \(O(NQ)\). In this problem, since \(N, Q \le 2 \times 10^5\), the worst case would require approximately \(4 \times 10^{10}\) operations, resulting in a Time Limit Exceeded (TLE) verdict.

Optimization Idea: “Skip Full Glasses”

For optimization, we consider the approach of “skipping glasses that are already full during subsequent searches.”

If we can efficiently determine “when champagne flows into glass \(i\), what is the first glass from glass \(i\) onward that is not yet full (has remaining capacity)?”, we can eliminate unnecessary scanning.

This can be solved in nearly constant time using Union-Find (with path compression).

Specifically, we manage groups for each glass \(i\) as follows: - Let parent[i] be “the index (representative) of the smallest glass from glass \(i\) onward that still has remaining capacity.” - In the initial state, all glasses have remaining capacity, so parent[i] = i. - The moment glass \(i\) becomes full, we merge glass \(i\)’s parent to “the representative of glass \(i+1\)’s group.”

This way, by simply calling find(i), we can instantly find the next glass that should receive champagne from glass \(i\) onward.

---

Algorithm

1. Data Preparation

• Array \(C\) storing the capacity of each glass
• Array amount storing the current champagne level of each glass (initially all 0)
• Array parent for Union-Find
  • Since we use 1-indexed management, the size is \(N+2\).
  • The \((N+1)\)-th element serves as a “sentinel (overflow tray)” for when all glasses are full and champagne overflows from the tower.

2. Processing Operation \(1\) (Pouring)

Pour \(V\) milliliters of champagne into the 1st glass.

1. Obtain the topmost “non-full glass” with curr = find(1).
2. While \(V > 0\) and curr <= N (within the tower’s range), repeat the following:
   • Calculate the remaining capacity of glass curr: space = C[curr] - amount[curr].
   • Case A: \(V \ge space\) (the glass becomes full)
     • Set glass curr’s champagne amount to full (C[curr]).
     • Update the pouring amount: \(V \leftarrow V - space\).
     • Since glass curr is now full, merge its parent to the adjacent glass’s group: parent[curr] = find(curr + 1).
     • Update the next pouring destination: curr = find(curr + 1).
   • Case B: \(V < space\) (the glass does not become full)
     • Pour all remaining champagne into glass curr: amount[curr] += V.
     • Set \(V = 0\) since there is no more champagne to pour, and exit the loop.

3. Processing Operation \(2\) (Query)

• Simply output the current amount of champagne in the \(k\)-th glass: amount[k].

---

Complexity

Time Complexity: \(O((N + Q) \alpha(N))\)

• The event of “a glass becoming full” occurs at most once per glass across the entire tower.
• Therefore, the number of Union-Find merges (parent updates) across all queries is at most \(N\).
• The Union-Find find operation, with path compression, runs in \(O(\alpha(N))\) (nearly constant time), where \(\alpha\) is the inverse Ackermann function.
• Thus, the overall time complexity is \(O((N + Q) \alpha(N))\), which comfortably fits within the time limit.

Space Complexity: \(O(N)\)

• The capacity array \(C\), current amount array amount, and Union-Find parent array are all of size \(O(N)\).
• Therefore, the space complexity is \(O(N)\).

---

Implementation Notes

• Introduction of a Sentinel (Level \(N+1\)): When the bottom glass at level \(N\) becomes full, we merge it to point to find(N + 1). This prevents out-of-bounds array access (Index Error) while also cleanly simulating the specification that “overflowed champagne is lost and does not accumulate anywhere.”

• Fast I/O in Python: Since Python has significant I/O overhead, we read all input at once using sys.stdin.read().split() and output using sys.stdout.write to batch the output, significantly reducing execution time.

  Source Code

import sys


def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    Q = int(input_data[1])

    # 1-indexedにするため、サイズは N + 2 とする
    C = [0] * (N + 2)
    for i in range(1, N + 1):
        C[i] = int(input_data[1 + i])

    # Union-Find（Disjoint Set Union）の初期化
    # parent[i] は、グラス i 以降でまだ満杯になっていない（空き容量がある）最小のグラスのインデックスを指す
    parent = list(range(N + 2))
    amount = [0] * (N + 2)

    def find(i):
        curr = i
        while parent[curr] != curr:
            curr = parent[curr]
        # 経路圧縮
        p = i
        while p != curr:
            nxt = parent[p]
            parent[p] = curr
            p = nxt
        return curr

    idx = N + 2
    out = []
    len_data = len(input_data)

    while idx < len_data:
        type_q = int(input_data[idx])
        if type_q == 1:
            V = int(input_data[idx + 1])
            idx += 2

            curr = find(1)
            while curr <= N and V > 0:
                space = C[curr] - amount[curr]
                if V >= space:
                    # グラス curr が満杯になる
                    amount[curr] = C[curr]
                    V -= space
                    # 満杯になったので、次の空いているグラスの代表元にマージする
                    nxt = find(curr + 1)
                    parent[curr] = nxt
                    curr = nxt
                else:
                    # グラス curr は満杯にならない
                    amount[curr] += V
                    V = 0
        else:
            k = int(input_data[idx + 1])
            idx += 2
            out.append(str(amount[k]))

    # まとめて出力
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

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