Overview

This problem asks us to find the total value of coins that Takahashi can collect along his path when moving from point \(S\) to point \(T\).

Analysis

Depending on the positional relationship between the starting point \(S\) and the destination \(T\), there are \(3\) patterns for Takahashi’s movement:

1. When \(S < T\) (moving to the right)
   • Points visited: \(S, S+1, S+2, \ldots, T\)
2. When \(S > T\) (moving to the left)
   • Points visited: \(S, S-1, S-2, \ldots, T\)
3. When \(S = T\) (no movement)
   • Points visited: only \(S\)

Upon careful observation, regardless of the direction of movement (right or left), the points Takahashi visits are “all integer points that are greater than or equal to the smaller of \(S\) and \(T\), and less than or equal to the larger of \(S\) and \(T\)”.

For example, both when \(S = 3, T = 7\) and when \(S = 7, T = 3\), the set of visited points is \(\{3, 4, 5, 6, 7\}\).

Therefore, if we let \(L = \min(S, T)\) and \(R = \max(S, T)\), Takahashi can pick up a coin placed at point \(P_i\) when the following condition is satisfied: $\(L \leq P_i \leq R\)$

Important Note

The number of points \(N\) can be as large as \(10^9\). Therefore, a naive simulation approach such as “managing all points in an array” would result in Memory Limit Exceeded (MLE) or Time Limit Exceeded (TLE). However, the number of coins \(M\) is at most \(2 \times 10^5\), which is sufficiently small. Instead of examining each point, we can efficiently solve the problem by “checking whether each coin falls within the collection range \(L \le P_i \le R\)” individually, without being affected by the size of \(N\).

Algorithm

1. From the starting point \(S\) and destination \(T\), compute the left boundary \(L = \min(S, T)\) and right boundary \(R = \max(S, T)\) of the movement range.
2. Initialize a variable total_value to \(0\) to hold the total value of collected coins.
3. Process the information of \(M\) coins one by one.
   • Read the coin’s position \(P_i\) and value \(V_i\) from input.
   • If \(L \leq P_i \leq R\) is satisfied, add \(V_i\) to total_value.
4. Output the final value of total_value.

Complexity

• Time Complexity: \(O(M)\) For each of the \(M\) coins, we determine whether it is within the range in \(O(1)\). Since \(M \leq 2 \times 10^5\), this comfortably fits within the time limit.
• Space Complexity: \(O(1)\) Since we do not store coin information in an array but instead judge and accumulate on the fly as we receive input, no extra memory is used.

Implementation Notes

• Data Types: Since points \(N, S, T, P_i\) can reach up to \(10^9\), they may exceed the range of \(32\)-bit integers in C++. For safety, we use long long type (\(64\)-bit integer type).

• Fast I/O: Since the number of input/output operations can be large, we include cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up C++ standard I/O.

  Source Code

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, M, S, T;
    if (!(cin >> N >> M >> S >> T)) return 0;

    long long L = min(S, T);
    long long R = max(S, T);

    long long total_value = 0;
    for (int i = 0; i < M; ++i) {
        long long P, V;
        cin >> P >> V;
        if (L <= P && P <= R) {
            total_value += V;
        }
    }

    cout << total_value << "\n";

    return 0;
}

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