Overview

This is a problem where we simulate “boarding → alighting (on the way to the next stop)” at each stop in order, and find the number of passengers immediately after boarding at the final stop \(N\).

Analysis

The key insight in this problem is that the state at each stop (the number of people on the bus) depends only on the “previous count,” and no detailed history of the past is needed.

At stop \(i\) (\(1 \le i \le N-1\)): - First, \(A_i\) people board, so the count increases by \(+A_i\) - Then \(B_i\) people alight, but if there aren’t enough passengers, everyone gets off
In other words, “if subtracting \(B_i\) from the count results in a negative number, set it to \(0\)”

Therefore, the update formula is: - \(p \leftarrow p + A_i\) - \(p \leftarrow \max(0, p - B_i)\)

If you naively “decrease the number of alighting people one by one,” since \(B_i\) can be up to \(10^9\), the loop would run too many times and cause TLE. However, in practice, you can subtract all at once and round to \(0\) if negative, processing it in \(O(1)\).

Note that at the final stop \(N\), only boarding occurs and no alighting happens.

(Example) When \(p=3\) with \(A_i=5, B_i=10\):
After boarding \(p=8\), at most 8 people can alight, so ultimately \(p=0\)
This matches the update formula \(p=\max(0, 8-10)=0\).

Algorithm

1. Start with passenger count \(p=0\).
2. Repeat for \(i=1\) to \(N-1\):
   • \(p \leftarrow p + A_i\)
   • \(p \leftarrow \max(0, p - B_i)\)
3. Finally, perform \(p \leftarrow p + A_N\) (no alighting at stop \(N\)).
4. Output \(p\).

Complexity

• Time complexity: \(O(N)\) (each stop is processed once)
• Space complexity: \(O(1)\) (only a constant number of variables like the passenger count are needed besides the input)

Implementation Notes

• The alighting process is equivalent to subtracting \(\min(p, B_i)\), so writing p = max(0, p - B_i) is concise.

• Since \(N\) can be up to \(2 \times 10^5\), in Python it is more stable to read input all at once using sys.stdin.buffer.read() for faster I/O.

• The input for stop \(N\) has a different format with only \(A_N\), so the loop runs \(N-1\) times and \(A_N\) is added at the end.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    idx = 1
    passengers = 0

    for _ in range(n - 1):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        passengers += a
        passengers = max(0, passengers - b)

    passengers += data[idx]
    print(passengers)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.