Overview

For each cloud height \(X\), only mountains with elevation \(A_i \geq X\) are visible.
For each contiguous interval of visible mountains, we take the maximum of \(B_i\), and for each query we compute the sum of these maxima.

Analysis

For a given cloud height \(X\), the visible mountains are those satisfying \(A_i \geq X\).

A naive approach would be to scan all mountains from left to right for each query, identifying contiguous intervals of visible mountains to find the answer.
However, this takes \(O(N)\) per query, resulting in \(O(NQ)\) overall.
Since \(N+Q \leq 2 \times 10^5\), this is too slow.

The key observation here is that as we decrease the cloud height from high to low, visible mountains only increase—they never disappear.

For example, when we lower the cloud height, newly visible mountains are added.
A newly added mountain connects to existing mountain ranges if its left or right neighbors are already visible.

In other words, we can manage this as follows:

• Mark visible mountains as “active”
• Treat adjacent active mountains as belonging to the same connected component
• Each connected component corresponds to one mountain range
• Maintain the maximum of \(B_i\) for each connected component
• The answer is the sum of maxima across all connected components

This can be efficiently managed using Union-Find (DSU).

Algorithm

Process queries in decreasing order of cloud height \(X\).
Also, sort the mountains in decreasing order of elevation \(A_i\).

For the current query with cloud height \(X\), add all mountains that haven’t been added yet and satisfy \(A_i \geq X\).

When adding mountain \(i\), perform the following operations:

1. Activate mountain \(i\)
2. Since mountain \(i\) alone forms a new mountain range, add \(B_i\) to the running total total
3. If the left neighbor \(i-1\) is active, merge them using Union-Find
4. If the right neighbor \(i+1\) is active, merge them using Union-Find

When merging two mountain ranges with scenic values \(m_1\) and \(m_2\) respectively, the scenic value after merging is:

\( \max(m_1, m_2) \)

Therefore, total is updated as follows:

\( total \leftarrow total - m_1 - m_2 + \max(m_1, m_2) \)

By maintaining the maximum of \(B_i\) within each connected component in the Union-Find, this update can be done efficiently.

Since queries are processed in decreasing order, but output must be in input order, we attach the original index to each query and store the answer in ans[original index].

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\)
  • Sorting mountains and queries takes \(O(N\log N + Q\log Q)\)
  • Union-Find operations are nearly \(O(1)\)
• Space complexity: \(O(N+Q)\)

Implementation Details

In the Union-Find, each connected component maintains the following information:

• parent: parent node
• sz: component size
• mx: maximum of \(B_i\) within that component

When adding a mountain, first create it as a standalone component:

dsu.mx[idx] = B[idx];
total += B[idx];

Then, if the left or right neighbors are already active, merge them:

if (idx > 0 && active[idx - 1]) {
    dsu.unite(idx, idx - 1, total);
}
if (idx + 1 < N && active[idx + 1]) {
    dsu.unite(idx, idx + 1, total);
}

During merging, it is important to subtract the maxima of the two components before merging from total, and add the maximum after merging.

Also, since the condition is \(A_i \geq X\), the check for adding a mountain is:

mountains[ptr].first >= X

Source Code

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    vector<long long> mx;

    DSU(int n) : parent(n), sz(n, 1), mx(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b, long long &total) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;

        total -= mx[ra];
        total -= mx[rb];

        if (sz[ra] < sz[rb]) swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
        mx[ra] = max(mx[ra], mx[rb]);

        total += mx[ra];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<long long> A(N), B(N);
    vector<pair<long long, int>> mountains(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        mountains[i] = {A[i], i};
    }

    vector<pair<long long, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        long long X;
        cin >> X;
        queries[i] = {X, i};
    }

    sort(mountains.begin(), mountains.end(), greater<>());
    sort(queries.begin(), queries.end(), greater<>());

    DSU dsu(N);
    vector<bool> active(N, false);
    vector<long long> ans(Q);

    long long total = 0;
    int ptr = 0;

    for (auto [X, qi] : queries) {
        while (ptr < N && mountains[ptr].first >= X) {
            int idx = mountains[ptr].second;

            active[idx] = true;
            dsu.parent[idx] = idx;
            dsu.sz[idx] = 1;
            dsu.mx[idx] = B[idx];

            total += B[idx];

            if (idx > 0 && active[idx - 1]) {
                dsu.unite(idx, idx - 1, total);
            }
            if (idx + 1 < N && active[idx + 1]) {
                dsu.unite(idx, idx + 1, total);
            }

            ptr++;
        }

        ans[qi] = total;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.