概要

各区間を順に進みながら体力を減らし、途中で一度でも体力が \(0\) 以下になったら以降は消費が倍になる、というルールをそのままシミュレーションして最終体力を求める問題です。

考察

重要な観察は次の2点です。

• 状態は「バテているかどうか」だけ
  未来の行動を変える要素は「すでにバテたか」の1ビットしかありません。一度バテたら戻らないため、各区間でやることは「今の状態に応じて体力を引く →（必要なら）バテ状態にする → 小屋があれば足す」の繰り返しです。
• 山小屋の情報を高速に参照できれば、前から1回走査で終わる
  各区間 \(i\) の直後に回復があるかどうかを毎回探す（例えば山小屋リストを線形探索する）と最悪で \(O(NM)\) になり、\(N, M \le 2 \times 10^5\) では間に合いません。
  そこで、回復量を rec[i]（区間 \(i\) の直後の回復量）として配列に入れておけば、各区間で \(O(1)\) で回復を足せます。

具体例（イメージ）： - ある区間でバテていない状態で体力を引いた結果 \(S \le 0\) になったら、その瞬間から「バテた状態」になります。 - その直後に山小屋があって回復し、体力が正に戻っても バテ状態は解除されません（以降ずっと消費が倍）。

このルール順（消費→バテ判定→回復）を崩すとWAになるので注意が必要です。

アルゴリズム

1. 入力で与えられる山小屋情報 \((P_j, R_j)\) を、配列 rec に格納する。
   
   • rec[i] = 区間 \(i\) 通過直後の回復量（なければ \(0\)）
2. tired = False（バテていない）で開始し、区間 \(i = 1..N\) を順に処理する。
   1. 体力消費：
      
      • tired == True なら \(S \leftarrow S - 2D_i\)
        
      • tired == False なら \(S \leftarrow S - D_i\)
   2. バテ判定：
      
      • tired == False かつ消費後に \(S \le 0\) なら tired = True
   3. 回復：
      
      • \(i < N\) のときだけ（最後の区間の後に小屋はない）、\(S \leftarrow S + rec[i]\)
3. ループ終了後の \(S\) を出力する（負でもそのまま）。

計算量

• 時間計算量: \(O(N + M)\)（回復配列の構築 \(M\)、シミュレーション \(N\)）
• 空間計算量: \(O(N)\)（回復配列 rec が主）

実装のポイント

• 処理順を厳守：消費 →（必要なら）バテ化 → 回復。回復してからバテ判定すると結果が変わります。

• 最後の区間の後は回復しない：問題文より区間 \(N\) 通過直後には山小屋が存在しないため、i < N のときだけ回復します。

• 山小屋の入力順はバラバラなので、rec[p] = r のように配列へ直接格納して対応します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    S = next(it)

    D = [next(it) for _ in range(N)]
    rec = [0] * (N + 1)  # rec[i]: recovery right after segment i (1..N-1)

    for _ in range(M):
        p = next(it)
        r = next(it)
        rec[p] = r

    tired = False
    for i in range(1, N + 1):
        di = D[i - 1]
        if tired:
            S -= 2 * di
        else:
            S -= di
            if S <= 0:
                tired = True

        if i < N:
            S += rec[i]

    print(S)

if __name__ == "__main__":
    main()

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