Overview

This problem is a simulation problem where we determine whether an electric vehicle can complete all \(N\) segments. We sequentially calculate the battery consumption for each segment and the recovery at charging stations located at specific positions.

Analysis

Important Rules

1. Driving condition: If the battery level is \(1\) or more immediately before driving segment \(i\), the vehicle can complete that segment.
2. Consumption: Driving segment \(i\) reduces the battery by \(D_i\).
3. Charging (swapping): Charging station \(j\) is located between segments \(P_j\) and \(P_j + 1\). In other words, it can be used immediately after completing segment \(P_j\). Swapping replaces the remaining battery level with \(S_j\).

Applying a Greedy Strategy

There is a choice of whether or not to swap the battery at a charging station, but this problem only asks whether the vehicle can complete all segments. Since a higher battery level makes it easier to complete the course, the greedy strategy of “always swap if the post-swap value \(S_j\) is greater than the current battery level” is optimal.

Failure Condition

During the simulation, if the battery level is \(0\) or less (less than \(1\)) when attempting to drive a segment, we can immediately determine that completion is impossible (No).

Algorithm

1. Set the current battery level to \(curr\_b = K\).
2. For segments \(i = 1, 2, \dots, N\), repeat the following:
   • If \(curr\_b < 1\), the vehicle cannot drive segment \(i\), so output No and terminate.
   • Drive segment \(i\) and reduce the battery: \(curr\_b = curr\_b - D_i\).
   • If there is a charging station immediately after segment \(i\) (i.e., \(i = P_j\)):
     • Compare the current level \(curr\_b\) with \(S_j\), and if \(S_j > curr\_b\), set \(curr\_b = S_j\).
3. After completing all segments, output Yes.

Complexity

• Time complexity: \(O(N + M)\)
  • We scan through all segments once and check each charging station’s information once, so the processing completes in time proportional to the input size.
• Space complexity: \(O(N + M)\)
  • This is the memory required to store the consumption values \(D_i\) for each segment and the charging station information in lists.

Implementation Notes

• Fast input: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Station management: Since charging stations are given in ascending order of \(P_j\), you can use a queue or pointer to efficiently determine whether a station exists immediately after the current segment.

• Negative battery levels: Even if \(curr\_b\) becomes \(0\) or less after driving a segment, if there is a charging station immediately after and the battery recovers to \(1\) or more there, the vehicle can still drive the next segment. Pay attention to the timing of the check (which is “immediately before” driving).

  Source Code

import sys

def solve():
    # Read all input tokens from standard input for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Use an iterator to process the tokens sequentially
    it = iter(input_data)
    
    # Read N (number of sections), M (number of charging stations), and K (initial battery)
    try:
        N = int(next(it))
        M = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # Read D_i: the battery consumption for each section i
    # D is stored in a list where D[0] corresponds to section 1, D[1] to section 2, etc.
    try:
        D = [int(next(it)) for _ in range(N)]
    except StopIteration:
        return
    
    # curr_b represents the current battery level of the electric vehicle
    curr_b = K
    
    # Stations are located between sections P_j and P_j + 1.
    # We store the next station's position (next_p) and its exchange value (next_s).
    if M > 0:
        try:
            next_p = int(next(it))
            next_s = int(next(it))
            stations_left = M - 1
        except StopIteration:
            next_p = None
            next_s = None
            stations_left = 0
    else:
        next_p = None
        next_s = None
        stations_left = 0
        
    # Iterate through all sections from 1 to N
    for i in range(1, N + 1):
        # Rule: If the battery level is 1 or more just before traveling, the car can travel the section.
        # If it is less than 1, the car stops and cannot travel the current section.
        if curr_b < 1:
            print("No")
            return
        
        # After traveling section i, the battery level decreases by D_i.
        curr_b -= D[i-1]
        
        # Charging stations are positioned after section P_j.
        # If the current section i is a station position, Takahashi can choose to exchange the battery.
        if next_p is not None and i == next_p:
            # Exchange is optimal only if the station's battery level is higher than the current level.
            if next_s > curr_b:
                curr_b = next_s
            
            # Load the next available station's information
            if stations_left > 0:
                try:
                    next_p = int(next(it))
                    next_s = int(next(it))
                    stations_left -= 1
                except StopIteration:
                    next_p = None
                    next_s = None
                    stations_left = 0
            else:
                next_p = None
                next_s = None
    
    # If the loop completes, it means Takahashi traveled all sections successfully.
    print("Yes")

if __name__ == "__main__":
    solve()

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