Overview

This problem asks us to travel from point \(0\) to \(G\) with initial fuel \(F\), using the minimum number of the \(N\) gas stations along the way. It can be efficiently solved using a greedy algorithm — “keep moving until you run out of fuel, and when you do, refuel at the station with the largest supply amount among all stations you’ve passed so far” — combined with a priority queue (heap).

Analysis

To reach the destination with the minimum number of refueling stops, it’s optimal to maximize the additional travel distance gained per refueling. However, it’s difficult to decide “should I refuel at this station now?” without knowing the supply amounts of future stations.

So we use the following reverse-thinking approach: 1. Move as far as possible: When passing a gas station, don’t refuel immediately — just carry the “right to refuel” and keep going. 2. Refuel when you run out: If you can’t reach the next destination (gas station or goal) with your current fuel, retroactively refuel at the passed station with the largest supply amount \(R_i\). 3. If that’s still not enough: Refuel at the station with the 2nd largest amount, then the 3rd largest, and so on, repeating until you can reach the next point. 4. If no candidates remain: If you still can’t reach the next point even after using all passed stations, it’s impossible to reach the goal (-1).

A max-heap (priority queue) is well-suited for efficiently performing the operation of “extracting the maximum from among the passed stations.”

Algorithm

1. Preprocessing: Sort the gas station information in ascending order of position \(P_i\).
2. Simulation:
   • Set the current reachable distance to current_reach = F and the refueling count to stops_count = 0.
   • Iterate through each gas station in order.
   • If the current station’s position \(P_i\) is farther than current_reach, extract the maximum value from the heap and add it to current_reach, incrementing the refueling count, repeating until the station becomes reachable.
   • Once the station’s position is reached, add its supply amount \(R_i\) to the heap.
3. Final check: After passing all gas stations, check whether the goal \(G\) is reachable. If not, repeat the refueling process from the heap in the same manner.
4. Output: If the goal is reachable, output stops_count; otherwise, output -1.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the gas stations takes \(O(N \log N)\).
  • For each gas station, heap push and pop operations are performed at most once each. Since each heap operation is \(O(\log N)\), the total is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • The gas station list and heap store at most \(N\) elements.

Implementation Notes

• Python’s heapq: Python’s heapq module implements a min-heap (extracts the smallest value first). To use it as a max-heap, a common technique is to store supply amounts \(R_i\) with a negated sign as -R_i, and negate the sign again after extraction.

• Large input: Since \(N = 2 \times 10^5\) and the input can be large, using sys.stdin.read().split() to read all input at once can reduce execution time.

• Goal check: At the end of the loop, you need to either treat the goal \(G\) as a “gas station with supply amount 0,” or add a separate check after the loop to verify whether the remaining distance to the goal can be covered.

  Source Code

import heapq
import sys

# 砂漠横断の問題を解くためのコード
# この問題は、優先度付きキューを用いた貪欲法（Greedy Algorithm）で解くことができます。
# 現在の燃料で到達可能な範囲にある給油所のうち、最も多くの燃料を補給できる場所を
# 選択することを繰り返すことで、立ち寄る給油所の数を最小限に抑えることができます。

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリスト化します。
    # 大規模な入力に対して高速に動作します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 給油所の個数, G: ゴールの位置, F: 初期の燃料
    N = int(input_data[0])
    G = int(input_data[1])
    F = int(input_data[2])
    
    # 各給油所の情報（位置 P_i と 補給量 R_i）を取得します。
    stations = []
    for i in range(N):
        p = int(input_data[3 + 2 * i])
        r = int(input_data[4 + 2 * i])
        stations.append((p, r))
    
    # 給油所を位置（P_i）の昇順にソートします。
    stations.sort()
    
    # 通過した給油所のうち、まだ燃料を補給していない場所の補給量を保持する最大ヒープ。
    # Pythonのheapqは最小ヒープなので、負の値を入れることで最大ヒープとして利用します。
    available_fuel = []
    current_reach = F
    stops_count = 0
    
    # 各給油所を順番に処理します。
    for pos, fuel in stations:
        # 現在の到達可能距離が次の給油所の位置に届かない場合、
        # これまでに通過した給油所の中から最も補給量が多い場所で給油します。
        while current_reach < pos:
            if not available_fuel:
                # どの給油所を使っても次の地点にたどり着けない場合
                print("-1")
                return
            # 最も燃料が多い給油所から補給
            current_reach += -heapq.heappop(available_fuel)
            stops_count += 1
        
        # 現在の給油所を「通過した給油所」としてヒープに追加します。
        heapq.heappush(available_fuel, -fuel)
        
    # 全ての給油所を処理した後、ゴール G に到達できるか確認します。
    while current_reach < G:
        if not available_fuel:
            # 残っている給油所を全て使ってもゴールに届かない場合
            print("-1")
            return
        # 未使用の給油所の中から最も燃料が多い場所で給油
        current_reach += -heapq.heappop(available_fuel)
        stops_count += 1
        
    # ゴールに到達するために必要な最小の給油回数を出力します。
    print(stops_count)

if __name__ == '__main__':
    solve()

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