Overview

This is a problem where you travel from start point \(0\) to destination \(G\), stopping at gas stations to refuel the minimum number of times, and output \(-1\) if the destination is unreachable.

Analysis

Key Insight

• It is impossible to exhaustively search “which gas stations to stop at” in advance (\(N \le 2\times 10^5\)).
• We need to manage, as we proceed, “among the gas stations we have passed so far, which one is the best to refuel at.”

Why Naive Approaches Are Difficult

• For example, exhaustively trying “stop/don’t stop” for each station would be \(2^N\), which is out of the question.
• Even with DP, the fuel amount can be as large as \(10^9\), causing the state space to explode.
• To find the “minimum number of stops,” we need to avoid wasteful refueling (refueling with small amounts) as much as possible.

How to Solve It (Greedy Strategy)

The following greedy approach works:

• Proceed from left to right (sort by position).
• When fuel runs out trying to reach a certain point, retroactively refuel at the passed gas station with the largest refuel amount \(R\).

Intuition behind this: - If we want to minimize the number of refuels, it is best to gain as much fuel as possible per refuel. - By choosing the maximum refuel from past candidates “at the moment we run out,” we maximize the reachable distance for the same number of refuels. - If we use a smaller one instead of the largest, we are likely to end up needing the largest one later anyway, increasing the total count.

To efficiently extract the “maximum \(R\) among past gas stations,” we use a max-heap (priority queue).

Concrete example: - If the refuel amounts of gas stations we’ve passed so far are \(\{4, 10, 3\}\) and we currently don’t have enough fuel, using \(10\) first is the most advantageous for minimizing the number of stops.

Algorithm

1. Sort gas stations \((P_i, R_i)\) in ascending order by position \(P_i\).
2. Add the destination as a “gas station with refuel amount \(0\)”: \((G, 0)\) (so that reaching \(G\) can be checked using the same logic).
3. Start with current fuel fuel \(= F\), previous position prev \(= 0\), and an empty max-heap (implemented as a min-heap with negated values) heap.
4. For each point pos in sorted order:
   • Subtract the fuel needed to reach it: fuel -= pos - prev
   • If fuel < 0, we cannot reach it, so extract the “largest past refuel amount” from heap and add it to fuel (= retroactively stop at that gas station). Repeat until fuel >= 0.
   • If fuel < 0 still holds (heap is empty), it is impossible to reach this point regardless, so output \(-1\).
   • If we can reach it, add this point’s refuel amount \(r\) to heap (adding it as a “candidate for future refueling if needed”).
   • Update prev = pos.
5. If all points are processed successfully, output the number of refuels made.

Key points: - It is important to “add a gas station to the candidates only after reaching it” (since using it before reaching it is impossible). - By adding the destination \((G, 0)\), the “last segment” can be handled with the same logic.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is \(O(N\log N)\) + at most a constant number of heap operations per gas station, totaling \(O(N\log N)\))
• Space complexity: \(O(N)\) (the heap contains at most \(N\) elements)

Implementation Notes

• Python’s heapq is a min-heap, so to use it as a max-heap, insert \(-R\) and negate the sign when extracting.

• Adding the destination \((G, 0)\) makes the implementation concise, avoiding the need to special-case “whether there is enough fuel to reach \(G\) at the end.”

• By “subtracting the travel cost first” with fuel -= pos - prev, we unify the logic into “if we can’t reach here, we must have refueled somewhere in the past.”

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, G, F = map(int, input().split())
    stations = [tuple(map(int, input().split())) for _ in range(N)]
    stations.sort()
    stations.append((G, 0))

    fuel = F
    prev = 0
    heap = []
    ans = 0

    for pos, r in stations:
        fuel -= pos - prev
        while fuel < 0 and heap:
            fuel += -heapq.heappop(heap)
            ans += 1
        if fuel < 0:
            print(-1)
            return
        heapq.heappush(heap, -r)
        prev = pos

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.