Overview

This problem requires answering \(Q\) queries on \(N\) given data points (mountain elevation and beauty), where each query asks for “the total beauty of mountains whose elevation is at least a certain value.”

Analysis

Naive Approach and Its Limitations

For each query, one could check every mountain one by one to determine if its elevation is at least \(L_j\) and compute the sum (linear search). However, this approach takes \(O(N)\) time per query, resulting in an overall time complexity of \(O(N \times Q)\). Given the constraints of this problem where \(N, Q \le 2 \times 10^5\), this would require up to approximately \(4 \times 10^{10}\) operations, which will not fit within the time limit.

Key Points for Optimization

To “quickly compute the sum over a specific range,” we combine the following two techniques:

1. Sorting and Binary Search: If we sort the mountains in ascending order of elevation, we can find “where the mountains with elevation at least \(L_j\) start” in \(O(\log N)\) using binary search.
2. Suffix Sum (from the back): By precomputing a suffix sum (reverse direction) that stores the total from a given position to the end, we can retrieve the sum over a range in \(O(1)\).

This allows us to answer each query in \(O(\log N)\).

Algorithm

1. Data Preparation: Pair each mountain’s elevation \(Y_i\) with its beauty \(P_i\), and sort by elevation \(Y\) in ascending order.
2. Suffix Sum Computation: For the sorted array of beauty values, create an array suffix_sums by accumulating totals from back to front.
   • suffix_sums[i] = (total beauty from the \(i\)-th element to the last in the sorted order)
   • It is convenient to set suffix_sums[N] = 0.
3. Answering Queries: For each threshold elevation \(L_j\), do the following:
   • Use binary search (in Python, bisect_left) to find the smallest index idx in the sorted elevation list where the value is at least \(L_j\).
   • suffix_sums[idx] is the desired answer.

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Sorting the mountains takes \(O(N \log N)\).
  • Building the suffix sum takes \(O(N)\).
  • \(Q\) binary searches take \(O(Q \log N)\).
• Space Complexity: \(O(N + Q)\)
  • Required to store the mountain data, the suffix sum array, and the query answers.

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python we use sys.stdin.read().split() and sys.stdout.write to eliminate I/O bottlenecks.

• Binary Search: To correctly handle cases where a mountain’s elevation is exactly \(L_j\), we use bisect_left to properly obtain the boundary for “at least \(L_j\).”

• Suffix Sum Indexing: By making the size of suffix_sums equal to \(N+1\), we ensure that even when no mountains satisfy the condition (idx = N), it returns 0 without causing an error.

  Source Code

import sys
from bisect import bisect_left

def solve():
    # 入力を一度にすべて読み込む（高速化のため）
    data = sys.stdin.read().split()
    if not data:
        return
    
    # すべての文字列を整数に変換
    nums = list(map(int, data))
    
    N = nums[0]
    Q = nums[1]
    
    # 山の標高(Y)と評価値(P)をスライスで抽出
    # Yはインデックス 2, 4, ..., 2 + 2*N - 2
    # Pはインデックス 3, 5, ..., 2 + 2*N - 1
    Y = nums[2:2+2*N:2]
    P = nums[3:2+2*N:2]
    
    # 標高 Y に基づいて山をソートする
    # zipを使用して (標高, 評価値) のペアを作成しソート
    mountains = sorted(zip(Y, P))
    
    # ソートされた結果から標高と評価値をそれぞれ分離
    if N > 0:
        heights, beauties = zip(*mountains)
    else:
        heights, beauties = (), ()
    
    # 評価値の累積和（後ろから）を計算
    # suffix_sums[i] は、ソート後の i 番目以降のすべての山の評価値の合計
    suffix_sums = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_sums[i] = suffix_sums[i+1] + beauties[i]
    
    # 調査（クエリ）の基準標高 L は、山のデータ以降に格納されている
    queries = nums[2+2*N:]
    results = []
    
    # 各調査に対して二分探索を用いて答えを求める
    for l in queries:
        # bisect_left で標高が l 以上となる最初のインデックスを取得
        idx = bisect_left(heights, l)
        # そのインデックス以降の評価値の合計を累積和配列から取得
        results.append(str(suffix_sums[idx]))
    
    # すべての答えを改行区切りで一括出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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