Overview

This problem asks you to find the sum of beauty ratings of mountains whose elevation is at least the specified threshold for each survey.

Analysis

A naive approach would be to scan all mountains for each survey, check their elevations, and sum up the ratings of mountains that satisfy the condition. However, since \(N\) and \(Q\) can each be up to \(2 \times 10^5\), this approach has a time complexity of \(O(NQ)\), requiring up to \(4 \times 10^{10}\) operations. This cannot be processed within the time limit.

To solve this problem efficiently, we need to preprocess the mountain data appropriately. Specifically, by sorting the mountains by elevation and precomputing prefix sums, we can process each query quickly.

Algorithm

1. Preprocessing: Sort all mountains in ascending order of elevation
2. Prefix sum computation: Compute the prefix sum of the beauty ratings of the sorted mountains
3. Query processing: For each query, do the following:
   • Use binary search to find the position of the first mountain with elevation at least \(L_j\)
   • Use the prefix sum to compute the total beauty rating from that position to the end

For example, if the mountains are sorted by elevation and we want to find the sum of beauty ratings from the \(i\)-th mountain onward, we can compute it as \(\text{prefix\_sum}[n] - \text{prefix\_sum}[i]\) using the prefix sum array \(\text{prefix\_sum}\).

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(\log N)\) per query for binary search, performed \(Q\) times giving \(O(Q \log N)\)
• Space complexity: \(O(N)\)
  • Arrays to store mountain data and prefix sums

Implementation Notes

• Use bisect.bisect_left() to efficiently find the position of the first mountain with elevation at least the specified threshold

• Creating the prefix sum array as 1-indexed makes range sum calculations intuitive (\(\text{prefix\_sum}[r] - \text{prefix\_sum}[l]\) gives the sum from index \(l\) to \(r-1\))

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

  Source Code

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    q = int(data[1])
    index = 2
    
    mountains = []
    for i in range(n):
        y = int(data[index])
        p = int(data[index+1])
        index += 2
        mountains.append((y, p))
        
    mountains.sort(key=lambda x: x[0])
    
    ys = [m[0] for m in mountains]
    ps = [m[1] for m in mountains]
    
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + ps[i]
    
    for i in range(q):
        l = int(data[index])
        index += 1
        
        pos = bisect.bisect_left(ys, l)
        total = prefix_sum[n] - prefix_sum[pos]
        print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.