Overview

This problem asks you to simulate the process of traversing each section in order while reducing stamina. If stamina drops to \(0\) or below at any point, all subsequent energy costs are doubled. You need to compute the final stamina.

Key Observations

The two important observations are:

• The only state is “whether you are exhausted or not”
  The only factor that affects future actions is a single bit: whether you have already become exhausted. Once exhausted, you never recover from that state. So for each section, the process is simply: “subtract stamina according to the current state → (if necessary) become exhausted → add recovery if there’s a mountain hut.”
• If mountain hut information can be looked up efficiently, a single forward scan suffices
  If you search the mountain hut list linearly for each section to check whether there’s a recovery point, the worst case becomes \(O(NM)\), which is too slow for \(N, M \le 2 \times 10^5\).
  Instead, by precomputing the recovery amount in an array rec[i] (the recovery amount right after section \(i\)), you can add the recovery in \(O(1)\) per section.

Concrete example (illustration): - If you are in the non-exhausted state and your stamina drops to \(S \le 0\) after subtracting the cost of a section, you become “exhausted” from that moment. - Even if there’s a mountain hut right after that section and your stamina recovers to a positive value, the exhausted state is NOT removed (energy costs remain doubled for the rest).

Be careful not to mix up the order of operations (cost → exhaustion check → recovery), as doing so will result in WA.

Algorithm

1. Store the mountain hut information \((P_j, R_j)\) from the input into an array rec.
   
   • rec[i] = recovery amount right after passing section \(i\) (\(0\) if none)
2. Start with tired = False (not exhausted) and process sections \(i = 1..N\) in order.
   1. Stamina consumption:
      
      • If tired == True: \(S \leftarrow S - 2D_i\)
        
      • If tired == False: \(S \leftarrow S - D_i\)
   2. Exhaustion check:
      
      • If tired == False and \(S \le 0\) after consumption: set tired = True
   3. Recovery:
      
      • Only when \(i < N\) (there is no hut after the last section): \(S \leftarrow S + rec[i]\)
3. Output the value of \(S\) after the loop ends (even if negative, output as is).

Complexity

• Time complexity: \(O(N + M)\) (building the recovery array: \(M\), simulation: \(N\))
• Space complexity: \(O(N)\) (mainly the recovery array rec)

Implementation Notes

• Strictly follow the processing order: consumption → (if necessary) become exhausted → recovery. If you check exhaustion after recovery, the result will differ.

• No recovery after the last section: According to the problem statement, no mountain hut exists right after section \(N\), so recovery is applied only when \(i < N\).

• Mountain hut input order may be arbitrary, so handle this by directly storing values as rec[p] = r into the array.

  Source Code

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

This editorial was generated by gpt-5.2-high.