Overview

This is a problem where \(N\) customers visit a single service counter in order, and we need to find the time when the last customer’s service is completed. Given each customer’s arrival time and the time required for their service, service begins at the earliest time when the counter is free and the customer has arrived.

Analysis

The key point of this problem is to simulate “when can the next customer’s service begin?” in order.

For customer \(i\)’s service to start, both of the following conditions must be satisfied: 1. The counter is free: The previous customer’s (customer \(i-1\)) service must have ended. 2. The customer has arrived: Customer \(i\) must have arrived at the office.

As stated in the problem, the service start time \(S_i\) for customer \(i\) is the later (\(\max\)) of the previous customer’s finish time \(S_{i-1} + B_{i-1}\) and the customer’s own arrival time \(A_i\).

Let’s consider concrete examples: - If the previous customer finishes at time \(10\) and the next customer arrives at time \(12\): The counter is free but the customer hasn’t arrived yet, so service starts at time \(12\). - If the previous customer finishes at time \(15\) and the next customer has already arrived at time \(12\): The customer is waiting but the counter is occupied, so service starts at time \(15\).

In this way, as long as we keep track of when the previous customer finishes, we can compute the answer sequentially.

Algorithm

1. Initialize a variable current_finish_time that holds the time when the counter becomes free to \(0\).
2. For \(i = 1\) to \(N\), repeat the following:
   • Read customer \(i\)’s arrival time \(A_i\) and service time \(B_i\).
   • Determine the service start time: start_time = max(current_finish_time, A_i).
   • Compute the service end time and update current_finish_time: current_finish_time = start_time + B_i.
3. The final value of current_finish_time is the answer.

Complexity

• Time complexity: \(O(N)\)
  • For each of the \(N\) customers, we perform constant-time operations (\(\max\) and addition), so the computation finishes in time proportional to the number of customers. Since \(N \leq 2 \times 10^5\), this is sufficiently fast.
• Space complexity: \(O(N)\) or \(O(1)\)
  • If all input is stored in a list or similar structure, it is \(O(N)\), but if we read and process one customer at a time, \(O(1)\) suffices.

Implementation Notes

• Fast I/O: In Python, since the number of customers \(N\) can be as large as \(2 \times 10^5\), it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Handling large numbers: The finish time can become a very large value on the order of \(10^9 + 10^9 \times (2 \times 10^5)\), but since Python natively supports arbitrary-precision integers, there is no need to worry about overflow.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してイテレータを作成します
    # これにより、大量の入力データに対しても高速に処理を行うことができます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 来客数 N を取得します
    try:
        N = int(next(it))
    except StopIteration:
        return
    
    # current_finish_time は窓口が次に空く時刻、
    # または直前の来客の対応が終了した時刻を保持します
    current_finish_time = 0
    
    for _ in range(N):
        # 各来客の到着時刻 A と対応にかかる時間 B を取得します
        A = int(next(it))
        B = int(next(it))
        
        # 来客 i の対応開始時刻 S_i は、窓口が空いている時刻と
        # 来客が到着した時刻のうち、遅い方の時刻になります
        # S_i = max(current_finish_time, A)
        if A > current_finish_time:
            current_finish_time = A
        
        # 来客 i の対応終了時刻は S_i + B です
        # これを次の来客のための current_finish_time として更新します
        current_finish_time += B
    
    # 最後の来客の対応が終了した時刻を出力します
    print(current_finish_time)

if __name__ == '__main__':
    solve()

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