Overview

This problem asks you to simulate the change in the number of passengers on a bus that visits \(N\) stops in order, and determine the number of passengers immediately after boarding at stop \(N\), the final destination.

Analysis

The key point of this problem is to process the events at each stop in order and accurately.

1. Boarding: Add \(A_i\) to the current number of passengers.
2. Alighting: Subtract \(B_i\) from the current number of passengers. However, since the number of passengers cannot become negative, if the result of subtraction is less than \(0\), correct it to \(0\).

From stop \(1\) to stop \(N-1\), both “boarding” and “alighting” are processed, and at the last stop \(N\), only “boarding” is performed.

Constraints and Complexity

The number of stops \(N\) is at most \(2 \times 10^5\). The processing at each stop consists only of addition, subtraction, and comparison with \(0\) (conditional branching), all of which can be done in constant time. Therefore, if we take a simulation approach that computes sequentially from start to finish, the overall time complexity is \(O(N)\), which is well within the time limit.

Also, while the passenger counts \(A_i\) and \(B_i\) can be as large as \(10^9\), the total number of passengers can potentially reach \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), so it is necessary to use a data type that can handle large integers (in Python, the standard integer type suffices).

Algorithm

The simulation is performed using the following steps:

1. Initialize a variable current_passengers representing the current number of passengers to \(0\).
2. For \(i = 1, 2, \dots, N-1\), repeat the following:
   • Add \(A_i\) to current_passengers.
   • Subtract \(B_i\) from current_passengers.
   • If current_passengers becomes less than \(0\), set current_passengers to \(0\).
3. Finally, add \(A_N\) to current_passengers.
4. Output the value of current_passengers.

Complexity

• Time Complexity: \(O(N)\)
  • Because we perform a loop proportional to the number of stops \(N\).
• Space Complexity: \(O(N)\)
  • If all input values are stored as lists, memory proportional to \(N\) is used.

Implementation Notes

• Reading Input: Since \(N\) can be large, in Python you can use sys.stdin.read().split() to read a large amount of input efficiently.

• Alighting Processing: You can concisely implement the “cannot become negative” condition by writing if current_passengers < 0: current_passengers = 0 after current_passengers -= B, or by using current_passengers = max(0, current_passengers - B).

• Loop Range: Since the last stop \(N\) does not have an alighting process (\(B_i\)), you need to either stop the loop after \(N-1\) iterations or use a conditional branch to handle the \(N\)-th stop separately.

  Source Code

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    current_passengers = 0
    idx = 1
    
    # 停留所 1 から N-1 までの処理
    for _ in range(N - 1):
        A = int(input_data[idx])
        B = int(input_data[idx + 1])
        idx += 2
        
        # 乗車
        current_passengers += A
        # 下車（0人を下回る場合は全員下車）
        current_passengers -= B
        if current_passengers < 0:
            current_passengers = 0
            
    # 停留所 N での乗車
    A_N = int(input_data[idx])
    current_passengers += A_N
    
    # 結果を出力
    print(current_passengers)

if __name__ == "__main__":
    solve()

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