Overview

Among points \(1\) to \(N\) arranged on a line, we need to find the cherry blossom trees contained in the interval \([S, T]\) (or \([T, S]\)) that Takahashi traverses, and compute the total number of petals.

Analysis

The key point for solving this problem is to accurately determine “which points Takahashi passes through.”

Takahashi travels the shortest distance from point \(S\) to point \(T\). - If \(S \leq T\): he passes through points \(S, S+1, \ldots, T\). - If \(S > T\): he passes through points \(S, S-1, \ldots, T\).

In either case, the points he passes through are all integer points in the range “at least \(\min(S, T)\) and at most \(\max(S, T)\).”

Important Note

The number of points \(N\) can be as large as \(10^9\), so an \(O(N)\) approach like “checking each point from \(1\) onwards” will not meet the time limit. On the other hand, since the number of cherry blossom trees \(M\) is around \(2 \times 10^5\), an \(O(M)\) approach of “checking each cherry blossom tree one by one” is fast enough.

Algorithm

1. Let the lower bound of the range Takahashi visits be \(low = \min(S, T)\) and the upper bound be \(high = \max(S, T)\).
2. Initialize a variable total_petals to \(0\) to hold the total number of petals.
3. For each of the \(M\) cherry blossom trees, perform the following:
   • Check whether the position \(P_i\) of the \(i\)-th cherry blossom tree satisfies \(low \leq P_i \leq high\).
   • If it does, add \(V_i\) to total_petals.
4. Output the final total_petals.

Complexity

• Time complexity: \(O(M)\)
  • Since we loop once for each of the \(M\) cherry blossom trees, the processing is fast and independent of the number of points \(N\).
• Space complexity: \(O(M)\)
  • This is needed when storing the information of the cherry blossom trees in a list or similar data structure.

Implementation Notes

• Handling large numbers: The total number of petals can reach up to \(M \times \max(V_i) \approx 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\). Python’s integer type (int) automatically handles arbitrary-precision integers, so you can compute without worrying about overflow.

• Fast I/O: Since \(M\) can be large, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), reducing execution time.

• Range checking: By using min and max to determine the boundaries of the travel range, the implementation handles both \(S < T\) and \(S > T\) cases simply.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにします。
    # これは大量の入力を高速に処理するための定石です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 地点の数 (この問題の解法には直接使用しません)
    # M: 桜の木の数
    # S: スタート地点
    # T: ゴール地点
    m = int(input_data[1])
    s = int(input_data[2])
    t = int(input_data[3])
    
    # 高橋君が移動する範囲を [low, high] として定めます。
    # 最短距離で移動するため、訪れる地点は min(S, T) から max(S, T) の間の全整数です。
    if s <= t:
        low, high = s, t
    else:
        low, high = t, s
        
    total_petals = 0
    
    # 桜の木の情報は input_data のインデックス 4 以降に P_i, V_i の順で並んでいます。
    # map(int, ...) を使って文字列を整数に変換するイテレータを作成します。
    it = map(int, input_data[4:])
    
    # イテレータから要素を2つずつ取り出して処理します（P_i: 地点, V_i: 花びらの枚数）。
    for p in it:
        try:
            v = next(it)
            # 桜の木の地点 p が移動範囲 [low, high] に含まれているか判定します。
            if low <= p <= high:
                total_petals += v
        except StopIteration:
            # 予期せぬ入力終了に対する安全策です。
            break
            
    # 合計の花びら枚数を出力します。
    # Pythonの整数型は非常に大きな値も扱えるため、オーバーフローの心配はありません。
    print(total_petals)

if __name__ == '__main__':
    solve()

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