Overview

This is a problem where, for each survey, we need to find “the sum of evaluation values \(P_i\) of mountains whose elevation is at least \(L_j\).” By cleverly sorting the mountains and queries and reusing the running total, we can answer efficiently.

Analysis

Key Insight

The larger the query \(L_j\) is, the fewer mountains satisfy the condition “\(Y_i \ge L_j\).” Conversely, as \(L_j\) decreases, the number of mountains satisfying the condition monotonically increases.

By leveraging this “monotonicity,” we realize that instead of scanning all mountains for each query, we only need to add newly qualifying mountains to the running total.

Why the Naive Approach Is Too Slow

If for each query we scan all mountains and - “add \(P_i\) if \(Y_i \ge L_j\)” the time complexity becomes \(O(NQ)\).

Since the maximum values are \(N=Q=2\times 10^5\), we get \(NQ=4\times 10^{10}\), which will not finish in a reasonable time (TLE).

Solution

• Sort the mountains in descending order of elevation
• Sort the queries in descending order of \(L_j\)
• Process from the largest \(L\) first, adding mountains that satisfy the condition “from the front” at each step

This way, each mountain is added to the total at most once, making the overall process fast.

Algorithm

1. Store the mountains as \((Y_i, P_i)\) in an array and sort in descending order of \(Y_i\).
2. For queries \(L_j\), store them as \((L_j, \text{original index } j)\) in an array and sort in descending order of \(L_j\).
3. Prepare variables:
   • \(s\): the sum of evaluation values of “mountains added so far (= mountains with elevation at least the current \(L\))”
   • \(i\): how many mountains have been processed from the front of the mountain array (the position of the next mountain to add)
4. Iterate through the queries in descending order. For each query \((l, idx)\):
   • Add as many mountains as possible from the front of the mountain array whose elevation is at least \(l\)
     (i.e., while i < N and mountains[i].Y >= l: s += mountains[i].P; i++)
   • The current value of \(s\) is “the sum of evaluation values of mountains satisfying \(Y_i \ge l\),” so store it in ans[idx].
5. Finally, output the answers in the original query order (restored using idx).

Concrete Example

Mountains (elevation, evaluation): \((10,5),(7,3),(3,4)\)
Queries: \(L=8,4\)

• Mountains in descending order: \((10,5),(7,3),(3,4)\)
• Queries in descending order: \(8,4\)

1. \(L=8\)
   Only \((10,5)\) has elevation \(\ge 8\) → \(s=5\)
   
2. \(L=4\)
   From the previous state, additionally add \((7,3)\) which satisfies elevation \(\ge 4\) → \(s=8\)
   The answers are \(5,8\) respectively.

The key point is “reusing the result from the previous query and only adding the difference.”

Complexity

• Time complexity: Sorting takes \(O(N\log N + Q\log Q)\), and the scan takes \(O(N+Q)\), so the overall complexity is \(O(N\log N + Q\log Q)\)
• Space complexity: \(O(N+Q)\) for the mountain, query, and answer arrays

Implementation Notes

• Since sorting the queries disrupts the output order, make sure to carry the “original index” along and store results in ans[idx] to restore the order.

• The total \(s\) can be as large as \(N \times 10^9\), but Python’s int supports arbitrary precision, so this is safe.

• Since the input is large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    Q = next(it)

    mountains = []
    for _ in range(N):
        y = next(it)
        p = next(it)
        mountains.append((y, p))
    mountains.sort(reverse=True)  # sort by height descending

    queries = []
    for idx in range(Q):
        l = next(it)
        queries.append((l, idx))
    queries.sort(reverse=True)  # sort by threshold descending

    ans = [0] * Q
    s = 0
    i = 0
    for l, idx in queries:
        while i < N and mountains[i][0] >= l:
            s += mountains[i][1]
            i += 1
        ans[idx] = s

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.