Overview

This is a mountain climbing simulation where you pass through \(N\) sections sequentially from the base to the summit. If your stamina drops to \(0\) or below, you enter an “exhausted state,” and from that point on, all stamina consumption is doubled. The goal is to determine your final remaining stamina.

Analysis

This problem is a simulation problem that does not require complex algorithms. You can obtain the correct answer by accurately implementing the rules described in the problem statement.

The key observations are as follows:

• Exhaustion is irreversible: Once you become exhausted, you do not recover from this state even if your stamina is restored. Therefore, the state transition is one-directional: “not exhausted → exhausted.”
• Order of processing matters: For each section, processing occurs in the order: ①stamina consumption → ②exhaustion check → ③mountain hut recovery. Getting this order wrong will lead to an incorrect answer.
• Exhaustion check happens right after consumption, before recovery: Since mountain hut recovery occurs after step ②, if your stamina drops to \(0\) or below from consumption, the exhaustion check is applied first, and then recovery is applied afterward.

For example, if you have stamina \(5\) and pass through a section with difficulty \(6\), your stamina becomes \(5 - 6 = -1\), which is \(0\) or below, so you enter the exhausted state. Even if you then recover \(10\) at a mountain hut bringing your stamina to \(9\), the exhausted state is not removed. From the next section onward, stamina consumption is doubled.

Since \(N \leq 2 \times 10^5\), an \(O(N)\) simulation processing each section one by one is more than sufficient.

Algorithm

1. Store the mountain hut information in an array recover. recover[i] is the recovery amount obtained immediately after passing through section \(i\) (or \(0\) if there is no mountain hut).
2. Initialize stamina stamina to the initial value \(S\) and state exhausted to False (not exhausted).
3. For each section from \(1\) to \(N\), do the following:
   • Stamina consumption: Subtract \(D_i\) from stamina if not exhausted, or \(2 \times D_i\) if exhausted.
   • Exhaustion check: If stamina is \(0\) or below and not yet exhausted, set the state to exhausted.
   • Mountain hut recovery: If recover[i] is greater than \(0\), add it to stamina.
4. Output the final stamina.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for reading the mountain hut information, \(O(N)\) for the section simulation.
• Space complexity: \(O(N)\)
  • \(O(N)\) each for the difficulty array \(D\) and the recovery array recover.

Implementation Notes

• Array representation for mountain huts: The mountain hut information is given as pairs \((P_j, R_j)\), and the order is not necessarily sorted. By preparing an array of size \(N+1\) and storing recover[P_j] = R_j, you can look up values in \(O(1)\) during the simulation.

• Be careful with the range of stamina: Since \(S\), \(D_i\), and \(R_j\) can be up to \(10^9\), stamina can take very large negative or positive values. Python handles arbitrary-precision integers so there is no concern about overflow, but in C++ and similar languages, you need to use long long.

• Fast input: Since \(N\) can be up to \(2 \times 10^5\), in Python we speed up input by reading everything at once using sys.stdin.buffer.read().

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    
    D = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    recover = [0] * (N + 1)  # recover[i] = recovery after section i
    for j in range(M):
        P = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        recover[P] = R
    
    stamina = S
    exhausted = False
    
    for i in range(1, N + 1):
        # Step 1: consume stamina
        if not exhausted:
            stamina -= D[i - 1]
        else:
            stamina -= 2 * D[i - 1]
        
        # Step 2: check if becomes exhausted
        if stamina <= 0 and not exhausted:
            exhausted = True
        
        # Step 3: mountain hut recovery
        if recover[i] > 0:
            stamina += recover[i]
    
    print(stamina)

main()

This editorial was generated by claude4.6opus-thinking.