Overview

Given \(N\) mountains, the problem asks to efficiently compute, for each of \(Q\) queries, the sum of beauty values of mountains whose elevation is at least a specified threshold \(L_j\).

Analysis

Naive Approach and Its Issues

The simplest method is to scan all mountains for each query and sum up \(P_i\) for mountains with elevation at least \(L_j\). In this case, each query takes \(O(N)\), resulting in \(O(NQ)\) overall. Since both \(N\) and \(Q\) can be up to \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, leading to TLE (Time Limit Exceeded).

Key Insight

Each query asks for “the sum of beauty values of mountains with elevation at least \(L_j\)”, which is in the form of the sum of elements above a certain threshold. If we sort the mountains by elevation, we can use binary search to quickly find “where the mountains with elevation at least \(L_j\) start”. Furthermore, if we precompute the sum of beauty values from that position to the end using a suffix sum, we can obtain the answer in \(O(1)\).

Concrete Example

Suppose there are 3 mountains, and after sorting by elevation they look like this:

The suffix sum suffix_sum is computed from the end: - suffix_sum[3] = 0 - suffix_sum[2] = 0 + 3 = 3 - suffix_sum[1] = 3 + 8 = 11 - suffix_sum[0] = 11 + 5 = 16

For a query \(L = 300\), binary search finds index \(1\), and the answer is suffix_sum[1] = 11 (the sum of beauty values of mountains with elevations 300 and 500).

Algorithm

1. Sort the mountains in ascending order of elevation \(Y_i\).
2. Build the suffix sum. Let suffix_sum[i] be the total beauty \(P\) of all mountains from sorted index \(i\) onward. Initialize suffix_sum[N] = 0, and compute in reverse order from \(i = N-1\) to \(0\): suffix_sum[i] = suffix_sum[i+1] + P_i.
3. Perform binary search for each query. Using bisect_left on the sorted elevation array, find the first index pos where the elevation is at least \(L_j\).
4. The answer is suffix_sum[pos]. If no such mountain exists (pos = N), then suffix_sum[N] = 0 is returned.

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • Sorting takes \(O(N \log N)\), building the suffix sum takes \(O(N)\), and binary search for each query takes \(O(\log N)\) repeated \(Q\) times for \(O(Q \log N)\).
• Space complexity: \(O(N)\)
  • For the sorted array and the suffix sum array.

Implementation Notes

• By using bisect_left, we can accurately find the first position with elevation at least \(L_j\). The reason for using bisect_left instead of bisect_right is to include mountains whose elevation is exactly equal to \(L_j\).

• By using a suffix sum, we can retrieve the sum “from a given position to the end” in \(O(1)\). This can also be achieved with a prefix sum from the beginning, but the suffix sum approach is more intuitive.

• Since \(P_i\) can be up to \(10^9\) and there can be up to \(2 \times 10^5\) mountains, the total can reach approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, long long must be used.

• For fast I/O, we read all input at once using sys.stdin.buffer.read() and output results collectively using '\n'.join().

  Source Code

import sys
import bisect

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    mountains = []
    for i in range(N):
        Y = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        mountains.append((Y, P))
    
    # Sort by elevation
    mountains.sort(key=lambda x: x[0])
    
    sorted_Y = [m[0] for m in mountains]
    
    # Build suffix sum array
    suffix_sum = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + mountains[i][1]
    
    out = []
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        # Find the first index where Y >= L
        pos = bisect.bisect_left(sorted_Y, L)
        out.append(str(suffix_sum[pos]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.