Overview

Find the total number of petals falling from cherry blossom trees located among points arranged on a straight line. Takahashi moves from point \(S\) to point \(T\) by the shortest distance and receives petals from cherry blossom trees at the points he passes through.

Analysis

In this problem, we need to sum up the corresponding number of petals for all cherry blossom trees within the interval from point \(S\) to point \(T\) that Takahashi traverses.

Naive Approach and Its Issues

A straightforward approach would be to scan all points from \(S\) to \(T\) and check each time whether there is a cherry blossom tree at that point. However, since the number of points \(N\) can be as large as \(10^9\), this method cannot finish within a realistic time limit (TLE).

Furthermore, since the input only provides the “points” where cherry blossom trees exist, it is also impossible to store all points in an array or similar structure beforehand.

Improvement: Interval Handling and Prefix Sums

Here is the key observation: - The movement is along a straight line, so the “traversed interval” can simply be considered as the interval \([\min(S,T), \max(S,T)]\). - If we know the positions of each cherry blossom tree, we only need to consider trees contained within this interval.

Therefore, we consider the following procedure: 1. Sort the cherry blossom tree positions. 2. We want to efficiently find tree positions within the interval \([\min(S,T), \max(S,T)]\) → binary search is effective. 3. We want to quickly compute the total petals for trees within that interval → using prefix sums, we can obtain partial sums in constant time.

This allows us to efficiently compute the answer even for very large \(N\).

Algorithm

1. Read the input and store the cherry blossom tree information as a list of \((P_i, V_i)\) pairs.
2. Sort the list in ascending order by tree position \(P_i\).
3. Precompute the prefix sums for the sorted petal counts \(V_i\).
4. Determine Takahashi’s movement interval \([start, end]\) as \(\min(S, T)\) and \(\max(S, T)\).
5. Using binary search (e.g., bisect_left), find the start and end indices of trees contained within the interval \([start, end]\).
6. Use the prefix sum table to quickly compute the total petals for the relevant interval and output the result.

Complexity

• Time complexity: \(O(M \log M)\) (primarily due to sorting)
• Space complexity: \(O(M)\)

※ \(M\) is the number of cherry blossom trees, at most \(2 \times 10^5\)

Implementation Notes

• Since the input can be very large, use fast input processing (e.g., sys.stdin.read()).

• bisect_left(a, x) returns the position where element x should be inserted in the sorted list a (pay attention to boundary conditions).

• When you want to obtain the sum of the interval \([L, R]\), using a prefix sum array cumsum, it can be computed as cumsum[R+1] - cumsum[L] (assuming cumsum[0] = 0).

  Source Code

import sys
from bisect import bisect_left

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    S = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    # 桜の木の位置を基準にソートするため、(位置, 花びら数) のリストを作成
    trees = []
    for _ in range(M):
        p = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        trees.append((p, v))
    
    # 位置でソート
    trees.sort()
    positions = [t[0] for t in trees]
    petals = [t[1] for t in trees]
    
    # 累積和を計算（前処理）
    cumsum = [0]
    for v in petals:
        cumsum.append(cumsum[-1] + v)
    
    # 開始点と終了点を範囲として統一（開始 < 終了にする）
    start, end = min(S, T), max(S, T)
    
    # 二分探索で範囲内の木のインデックスを取得
    left_idx = bisect_left(positions, start)
    right_idx = bisect_left(positions, end + 1)
    
    # 累積和を使って範囲内の合計を高速に計算
    total = cumsum[right_idx] - cumsum[left_idx]
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.