Overview

This is a problem where a bus visits N stops in order, with passengers boarding and alighting at each stop, and we need to find the number of passengers after boarding is completed at the final stop.

Analysis

A straightforward simulation of the process at each stop can be considered, but since the number of stops N can be up to 200,000, efficient processing is necessary. The key observation is that the alighting process removes “the smaller of the current number of passengers and B_i.” In other words, if the current number of passengers is less than B_i, everyone alights, and otherwise only B_i people alight. By leveraging this property and processing the stops in order, we can compute the answer efficiently.

Algorithm

1. Initialize the current number of passengers to 0
2. For the first N-1 stops, repeat the following:
   • Add A_i to the current number of passengers (boarding process)
   • If the current number of passengers is less than B_i, set it to 0; otherwise, subtract B_i (alighting process)
3. At the last stop, add A_N (boarding only)
4. Output the final number of passengers

In this algorithm, the processing at each stop takes constant time, so the overall computation runs in O(N) time.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the input data)

Implementation Notes

• Pay attention to the input format: the last stop does not have a B_i

• Properly update the variable current that manages the current number of passengers

• For the alighting process, use conditional branching for efficient processing instead of min(current, B_i)

• Be careful about integer overflow (not an issue in Python)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = []
    B = []
    index = 1
    for i in range(n-1):
        A.append(int(data[index]))
        B.append(int(data[index+1]))
        index += 2
    A.append(int(data[index]))
    
    current = 0
    for i in range(n-1):
        current += A[i]
        if current < B[i]:
            current = 0
        else:
            current -= B[i]
    
    current += A[-1]
    print(current)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.