概要

一直線上の地点 \(S\) から \(T\) まで最短で移動するとき、通過（到着・出発地点も含む）する区間内にある桜の木の \(V_i\) を合計する問題です。

考察

一直線上で「最短距離で移動する」とき、道は一意に決まります。
つまり、高橋君が通る地点は \(S\) と \(T\) の間（両端含む）にある地点すべて です。

• 例えば \(S=3, T=7\) なら、通る地点は \(3,4,5,6,7\)。
• 例えば \(S=8, T=5\) なら、通る地点は \(8,7,6,5\) で、結局 地点集合としては \([5,8]\)。

したがって「花びらが落ちるかどうか」は、各木について - その木の位置 \(P_i\) が \([ \min(S,T), \max(S,T) ]\) に入るか

だけで判定できます。

素朴に「移動を1歩ずつシミュレーションして通った地点を数える」方法は、距離が最大で \(|S-T| \le 10^9\) になり得るため \(O(N)\) になってしまい、時間的に実行できません（TLE）。
一方で桜の木の本数は \(M \le 2 \times 10^5\) なので、木を1本ずつ見て区間内か判定するのが効率的です。

アルゴリズム

1. \(l = \min(S, T)\)、\(r = \max(S, T)\) を計算する。
2. 答え \(ans = 0\) を用意する。
3. 各桜の木 \((P_i, V_i)\) について、もし \(l \le P_i \le r\) なら \(ans += V_i\)。
4. \(ans\) を出力する。

このとき、スタート地点 \(S\) やゴール地点 \(T\) に木がある場合も、区間 \([l,r]\) に含まれるため自然に加算されます。

計算量

• 時間計算量: \(O(M)\)（木を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（入力を逐次処理して合計するだけ）

実装のポイント

• \(S < T\) の場合も \(S > T\) の場合も同じ処理にするため、先に \(l=\min(S,T), r=\max(S,T)\) を作るのが簡潔です。

• \(V_i\) や合計は最大で \(2\times 10^5 \times 10^9 = 2\times 10^{14}\) になり得ますが、Python の int は多倍長整数なのでそのままで安全です。

• 入力が大きいので、sys.stdin.buffer.read().split() を使うと高速に読み取れます。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。