概要

入会金の加算と飲料水購入費の減算を時系列にそのまま反映して最終残高（理論値）を求め、そこから実際の残高 \(R\) を引いた差額を出力する問題です。

考察

各イベントは残高に対して「足す」か「引く」かのどちらかしか起こりません。したがって、初期残高 \(S\) からスタートして、イベントを順番に処理していけば理論値が一意に定まります。

ここで重要なのは、購入イベントが「本数 \(v_i\)」で与えられており、差し引かれる金額が \(v_i \times P\) 円になる点です。つまりイベントごとに - \(e_i=1\) なら \(+v_i\) - \(e_i=2\) なら \(-v_i \times P\) を残高に反映すればよいだけです。

素朴に「イベントを全部シミュレーションする」方法がそのまま最適です。\(M \le 2\times 10^5\) なので、1 回ずつ処理しても十分間に合います（\(O(M)\)）。
逆に、例えば購入を「1 本ずつ」処理してしまうと、\(v_i\) が最大 \(10^5\) のため最悪で合計 \(10^{10}\) 回規模になり、TLE になります。購入は必ず まとめて \(v_i \times P\) を引く必要があります。

最後に、問題は（理論値）\(-R\) を求めるだけなので、理論値を求めた後に \(R\) を引いて出力します（（理論値）\(\ge R\) は保証済み）。

アルゴリズム

1. 残高 bal を \(S\) で初期化する。
2. \(i=1\) から \(M\) までイベントを順に読む。
   • \(e_i=1\)（入会）なら bal += v_i
   • \(e_i=2\)（購入）なら bal -= v_i * P
3. 最終的な理論値は bal。答えとして bal - R を出力する。

（例）\(S=1000, P=120\)、イベントが
- 入会 \(+500\) → \(1500\)
- 購入 \(3\) 本 → \(1500-3\times120=1140\)
なら理論値は \(1140\)、実残高が \(R=1000\) なら差額は \(1140-1000=140\) です。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\)（入力を逐次処理する場合）

実装のポイント

• 金額は最大で \(10^{18}\) 近くまで行き得るため、Python の int のような 64bit を超えない/超えても安全な整数型で扱う（Python なら問題なし）。

• 入力が最大 \(2\times 10^5\) 行あるので、sys.stdin.buffer.read() などで高速に読むと安全です。

• 購入イベントは必ず v * P を一度に計算して引き、1 本ずつループしないようにします。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。