Overview

This problem asks you to reflect membership fee additions and beverage purchase subtractions chronologically to compute the final balance (theoretical value), then output the difference between that and the actual balance \(R\).

Analysis

Each event either “adds to” or “subtracts from” the balance. Therefore, starting from the initial balance \(S\) and processing events in order uniquely determines the theoretical value.

The key point here is that purchase events are given as “number of bottles \(v_i\)”, and the amount deducted is \(v_i \times P\) yen. In other words, for each event: - If \(e_i=1\), add \(+v_i\) - If \(e_i=2\), subtract \(-v_i \times P\)

from the balance.

A straightforward “simulate all events” approach is optimal as-is. Since \(M \le 2\times 10^5\), processing each event one at a time is more than fast enough (\(O(M)\)). Conversely, if you process purchases “one bottle at a time”, since \(v_i\) can be up to \(10^5\), the worst case would be on the order of \(10^{10}\) total operations, resulting in TLE. Purchases must always be handled by subtracting \(v_i \times P\) all at once.

Finally, the problem simply asks for (theoretical value) \(- R\), so after computing the theoretical value, subtract \(R\) and output the result (it is guaranteed that (theoretical value) \(\ge R\)).

Algorithm

1. Initialize balance bal to \(S\).
2. Read events sequentially from \(i=1\) to \(M\).
   • If \(e_i=1\) (membership), then bal += v_i
   • If \(e_i=2\) (purchase), then bal -= v_i * P
3. The final theoretical value is bal. Output bal - R as the answer.

(Example) \(S=1000, P=120\), with events: - Membership \(+500\) → \(1500\) - Purchase of \(3\) bottles → \(1500-3\times120=1140\)

Then the theoretical value is \(1140\), and if the actual balance is \(R=1000\), the difference is \(1140-1000=140\).

Complexity

• Time complexity: \(O(M)\)
• Space complexity: \(O(1)\) (when processing input sequentially)

Implementation Notes

• Amounts can reach up to nearly \(10^{18}\), so use an integer type that is safe beyond 64 bits like Python’s int (no issues in Python).

• Since there can be up to \(2\times 10^5\) lines of input, it is safer to read input efficiently using something like sys.stdin.buffer.read().

• For purchase events, always compute v * P at once and subtract it; do not loop one bottle at a time.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    S = int(next(it))
    P = int(next(it))
    R = int(next(it))
    M = int(next(it))

    bal = S
    for _ in range(M):
        e = int(next(it))
        v = int(next(it))
        if e == 1:
            bal += v
        else:
            bal -= v * P

    print(bal - R)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.