Overview

This is a problem where you move from point \(S\) to point \(T\) on a straight line via the shortest path, and sum up the \(V_i\) values of cherry blossom trees located within the intervals you pass through (including the departure and arrival points).

Analysis

When “moving the shortest distance” on a straight line, the path is uniquely determined. In other words, the points Takahashi passes through are all points between \(S\) and \(T\) (inclusive of both endpoints).

• For example, if \(S=3, T=7\), the points passed are \(3,4,5,6,7\).
• For example, if \(S=8, T=5\), the points passed are \(8,7,6,5\), which as a set of points is \([5,8]\).

Therefore, whether “petals fall” can be determined for each tree by simply checking: - Whether the tree’s position \(P_i\) falls within \([\min(S,T), \max(S,T)]\)

A naive approach of “simulating the movement step by step and counting passed points” would result in \(O(N)\) since the distance can be up to \(|S-T| \le 10^9\), making it too slow (TLE). On the other hand, since the number of cherry blossom trees is \(M \le 2 \times 10^5\), it is efficient to check each tree one by one to see if it falls within the interval.

Algorithm

1. Compute \(l = \min(S, T)\) and \(r = \max(S, T)\).
2. Initialize the answer \(ans = 0\).
3. For each cherry blossom tree \((P_i, V_i)\), if \(l \le P_i \le r\), then \(ans += V_i\).
4. Output \(ans\).

In this case, if there is a tree at the starting point \(S\) or the goal point \(T\), it is naturally included in the interval \([l,r]\) and added to the sum.

Complexity

• Time complexity: \(O(M)\) (just examining each tree once)
• Space complexity: \(O(1)\) (just processing input sequentially and accumulating the sum)

Implementation Notes

• To handle both the \(S < T\) case and the \(S > T\) case with the same logic, it is concise to first compute \(l=\min(S,T), r=\max(S,T)\).

• \(V_i\) and the total sum can be as large as \(2\times 10^5 \times 10^9 = 2\times 10^{14}\), but since Python’s int is an arbitrary-precision integer, this is safe as-is.

• Since the input can be large, using sys.stdin.buffer.read().split() allows for faster reading.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    S = int(next(it))
    T = int(next(it))

    l = S if S < T else T
    r = T if S < T else S

    ans = 0
    for _ in range(M):
        p = int(next(it))
        v = int(next(it))
        if l <= p <= r:
            ans += v

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.