概要

各調査で「標高が \(L_j\) 以上の山の評価値 \(P_i\) の総和」を求める問題です。山とクエリをうまく並べ替えて、合計を使い回すことで高速に答えます。

考察

重要な気づき

クエリ \(L_j\) が大きいほど、条件「\(Y_i \ge L_j\)」を満たす山の数は減ります。逆に、\(L_j\) を小さくしていくと、条件を満たす山が単調に増えていきます。

この「単調性」を利用すると、各クエリごとに毎回山を全探索しなくても、追加される山だけを合計に足していけばよいと分かります。

素朴な方法が遅い理由

各クエリごとに全ての山を見て - 「\(Y_i \ge L_j\) なら \(P_i\) を足す」 をすると、時間計算量は \(O(NQ)\) になります。

最大で \(N=Q=2\times 10^5\) なので、\(NQ=4\times 10^{10}\) となり、現実的な時間では終わりません（TLE）。

解決策

• 山を標高の降順にソート
• クエリも \(L_j\) の降順にソート
• 大きい \(L\) から順に処理し、その時点で条件を満たす山を「先頭から」追加していく

こうすると、各山は高々1回だけ合計に加算され、全体が高速になります。

アルゴリズム

1. 山を \((Y_i, P_i)\) の形で配列に入れ、\(Y_i\) の降順にソートする。
2. クエリ \(L_j\) について、\((L_j, 元の番号j)\) の形で配列に入れ、\(L_j\) の降順にソートする。
3. 変数
   • \(s\): 「現在までに追加した山（= 今処理中の \(L\) 以上の山）」の評価値合計
   • \(i\): 山配列の先頭から何個見たか（次に追加すべき山の位置） を用意する。
4. クエリを降順に見ていき、各クエリ \((l, idx)\) について
   • 山配列の先頭から、標高が \(l\) 以上の山を追加できるだけ追加する
     （つまり while i < N and mountains[i].Y >= l: s += mountains[i].P; i++）
   • この時点の \(s\) が「\(Y_i \ge l\) を満たす山の評価値合計」なので、答え配列の ans[idx] に入れる。
5. 最後に、元のクエリ順に答えを出力する（idx を使って戻している）。

具体例

山（標高, 評価）: \((10,5),(7,3),(3,4)\)
クエリ: \(L=8,4\)

• 山を降順: \((10,5),(7,3),(3,4)\)
• クエリを降順: \(8,4\)

1. \(L=8\)
   標高 \(\ge 8\) は \((10,5)\) だけ → \(s=5\)
   
2. \(L=4\)
   前回の状態から追加で標高 \(\ge 4\) を満たす \((7,3)\) を足す → \(s=8\)
   答えはそれぞれ \(5,8\)。

「前のクエリの結果を再利用して、追加分だけ足す」のがポイントです。

計算量

• 時間計算量: ソートに \(O(N\log N + Q\log Q)\)、走査は \(O(N+Q)\) なので全体で \(O(N\log N + Q\log Q)\)
• 空間計算量: 山・クエリ・答え配列で \(O(N+Q)\)

実装のポイント

• クエリをソートすると出力順が崩れるため、必ず「元の番号」を一緒に持っておき、ans[idx] に入れて復元します。

• 合計値 \(s\) は最大で \(N \times 10^9\) 程度になり得ますが、Python の int は多倍長なので安全です。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。