Overview

This is a simulation problem where Takahashi passes through \(N\) sections in order while heading toward the summit. We need to correctly execute the series of operations—stamina consumption in each section, transition to the exhausted state, and recovery at mountain huts—according to the rules, and determine the final stamina.

Analysis

The key point of this problem is to accurately simulate the conditions for becoming “exhausted” and its subsequent effects.

1. State Transition and Irreversibility

Takahashi’s state is a one-way transition from “not exhausted” to “exhausted.” Once he becomes exhausted, no matter how much stamina he recovers at subsequent mountain huts, the penalty of consuming \(2 \times D_i\) stamina is never removed.

2. Order of Operations

The order of the 3 steps performed in each section \(i\) is extremely important: 1. Consumption: Decrease stamina based on the current state. 2. Check: If stamina after consumption is \(0\) or less, set the exhausted state. 3. Recovery: If there is a mountain hut, recover stamina.

In particular, even if “stamina drops to \(0\) or below right after consumption, but returns to positive after recovery,” the exhaustion check is performed at step 2, so Takahashi becomes exhausted. Getting this order wrong will produce incorrect results.

3. Managing Mountain Huts

The mountain hut information \((P_j, R_j)\) needs to be referenced efficiently using the section number \(P_j\) as a key. Since \(N\) can be up to \(2 \times 10^5\), linearly searching through the entire mountain hut list during each section’s processing would result in \(O(N \times M)\), which would not meet the time limit. We should prepare an array or associative array (dictionary) so that we can determine in \(O(1)\) whether a mountain hut exists after a particular section.

Algorithm

The simulation is performed with the following steps:

1. Preparation:
   • Store the difficulty of each section in an array \(D\).
   • Prepare an array huts of length \(N+1\), and record the recovery amount of each mountain hut as huts[P_j] = R_j (locations without a mountain hut have value \(0\)).
2. Initialization:
   • stamina = S
   • is_tired = False
3. Simulation:
   • Iterate sequentially from \(i = 1\) to \(N\):
     • Consumption: If is_tired is true, stamina -= 2 * D[i]; otherwise, stamina -= D[i].
     • Check: If is_tired is false and stamina <= 0, update is_tired = True.
     • Recovery: stamina += huts[i].
4. Output:
   • Output the final stamina.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading input and storing mountain hut data takes \(O(N + M)\).
  • The simulation part is \(O(N)\) since we process each of the \(N\) sections once in a loop.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the section difficulties \(D\) and the mountain hut recovery amounts huts.

Implementation Notes

• Handling Large Numbers: Stamina and difficulty values can be up to \(10^9\), and the final stamina may become a very large negative value or greatly exceed the initial stamina. In Python, there is no limit on integer size, so this is not a problem. However, when using other languages (such as C++ or Java), you need to use 64-bit integer types (long long or long).

• Fast I/O: Since \(N\) and \(M\) can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # Read all input at once and convert to integers for efficiency
    try:
        data = list(map(int, sys.stdin.read().split()))
    except EOFError:
        return
    
    if not data:
        return
    
    # N: number of segments, M: number of mountain huts, S: initial stamina
    N = data[0]
    M = data[1]
    S = data[2]
    
    # D: list of difficulties for each segment (D_1 to D_N)
    # They are located from index 3 to 3 + N - 1 in the data list.
    D = data[3 : 3 + N]
    
    # huts: recovery amount at the end of each segment
    # huts[i] stores the recovery amount R_j if a hut is located after segment i (P_j = i).
    # Since P_j is between 1 and N-1, a list of size N+1 is sufficient.
    huts = [0] * (N + 1)
    
    # Offset where the hut information (P_j, R_j) begins
    offset = 3 + N
    for i in range(M):
        p = data[offset + 2 * i]
        r = data[offset + 2 * i + 1]
        huts[p] = r
        
    stamina = S
    is_tired = False
    
    # Simulate the process for each segment from 1 to N
    for i in range(1, N + 1):
        # difficulty of the current segment
        d = D[i - 1]
        
        # 1. Stamina consumption
        if is_tired:
            # If already tired, stamina consumption is doubled
            stamina -= 2 * d
        else:
            # If not tired, stamina consumption is normal
            stamina -= d
            
            # 2. Fatigue check
            # If stamina becomes 0 or less after consumption, the state changes to tired.
            if stamina <= 0:
                is_tired = True
        
        # 3. Recovery at mountain hut (if any)
        # Recovery occurs after the segment is passed and fatigue check is completed.
        stamina += huts[i]
        
    # Output the final remaining stamina
    print(stamina)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-thinking.