Overview

For a threshold value \(K\), products with \(A_i < K\) are considered “defective,” and the problem asks us to compute the sum of the maximum \(B_i\) values for each contiguous interval of defective products.

Processing each query independently is too slow, so we process queries in ascending order of \(K\), gradually adding products that become defective.

Analysis

First, assume a fixed threshold value \(K\).

Defective products are those with \(A_i < K\). Only consecutive defective products in the original order can be placed in the same box.

For example, suppose defective products are arranged as follows:

defective defective good defective defective defective good defective

In this case, the contiguous intervals of defective products are the following \(3\):

[defective defective], [defective defective defective], [defective]

It is optimal to put all defective products within the same contiguous interval into a single box.

The reason is that the shipping cost of a box is “the maximum \(B_i\) among products in that box.”

If the maximum weight of a contiguous interval is \(M\), then putting the entire interval into one box costs \(M\).

If the interval is split into multiple boxes, the box containing the maximum weight \(M\) alone costs at least \(M\), and the other boxes also have positive costs, so the total is at least \(M\).

Therefore, the minimum shipping cost is:

The sum of the maximum \(B_i\) values within each contiguous interval of defective products.

---

Naively scanning all products for each query gives a time complexity of \(O(NQ)\).

Given the constraint \(N + Q \leq 2 \times 10^5\), the worst case is around \(O(10^{10})\), which is too slow.

So we process queries in ascending order of \(K\).

As \(K\) increases, the set of products satisfying \(A_i < K\) only grows and never shrinks.

In other words, the set of defective products monotonically increases.

Using this property, we examine products in ascending order of \(A_i\) and only add products that newly become defective for each query.

The contiguous intervals of defective products can be managed with a Union-Find.

When the product at position \(i\) newly becomes defective:

• First, add it as a standalone interval
• If the left neighbor \(i-1\) is already defective, merge them
• If the right neighbor \(i+1\) is already defective, merge them

By maintaining the maximum \(B_i\) within each contiguous interval, we can also update the total answer.

Algorithm

Each contiguous interval is treated as a connected component in Union-Find.

For each connected component, we maintain the following information:

• Parent parent
• Size sz
• Maximum \(B_i\) within that interval compMax

We also maintain the current answer as cur.

cur is the sum of compMax over all current contiguous intervals of defective products.

---

The processing steps are as follows:

1. Store products as \((A_i, i)\) and sort in ascending order of \(A_i\)
2. Store queries as \((K_j, j)\) and sort in ascending order of \(K_j\)
3. Prepare a pointer ptr pointing to products not yet added as defective
4. Process each query \(K\) in ascending order:
   • Add products satisfying \(A_i < K\) in order
   • Activate position pos as defective
   • Add a standalone interval with cur += B[pos]
   • If the left neighbor is active, merge using Union-Find
   • If the right neighbor is active, merge using Union-Find
   • During merging, subtract the old intervals’ maximum values from cur and add the new interval’s maximum value
5. The current value of cur is the answer for that query
6. Since queries are processed in sorted order, restore the original order before outputting

---

The update during merging works as follows:

Let \(x\) and \(y\) be the maximum values of the two intervals. Before merging, the answer includes \(x + y\).

After merging, they become one interval with maximum value \(\max(x, y)\).

Therefore, we update:

\[ cur \leftarrow cur - x - y + \max(x, y) \]

In the code, this is done inside the unite function.

Complexity

• Time complexity: \(O((N + Q)\log(N + Q))\)
• Space complexity: \(O(N + Q)\)

Sorting products and queries takes \(O(N\log N + Q\log Q)\).

Union-Find operations are nearly constant time, totaling \(O(N \alpha(N))\) overall. Here, \(\alpha(N)\) is the inverse Ackermann function, which is practically constant.

Implementation Notes

• Since the condition is \(A_i < K\), the addition condition must also be A < K.

• Since queries are sorted for processing, we store the original indices alongside them.

• To determine whether the left or right neighbor of position pos is already defective, we prepare an active[pos] array.

• The answer can be as large as \(N \times 10^9\), so long long must be used.

  Source Code

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

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

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

    vector<long long> B(N);
    vector<tuple<long long, int>> items;
    items.reserve(N);

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

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

    sort(items.begin(), items.end());
    sort(queries.begin(), queries.end());

    vector<int> parent(N), sz(N, 1);
    vector<long long> compMax(N, 0);
    vector<char> active(N, 0);

    iota(parent.begin(), parent.end(), 0);

    auto find_root = [&](auto&& self, int x) -> int {
        if (parent[x] == x) return x;
        return parent[x] = self(self, parent[x]);
    };

    long long cur = 0;

    auto unite = [&](int x, int y) {
        int rx = find_root(find_root, x);
        int ry = find_root(find_root, y);
        if (rx == ry) return;

        cur -= compMax[rx];
        cur -= compMax[ry];

        if (sz[rx] < sz[ry]) swap(rx, ry);
        parent[ry] = rx;
        sz[rx] += sz[ry];
        compMax[rx] = max(compMax[rx], compMax[ry]);

        cur += compMax[rx];
    };

    vector<long long> ans(Q);
    int ptr = 0;

    for (auto [K, qi] : queries) {
        while (ptr < N && get<0>(items[ptr]) < K) {
            int pos = get<1>(items[ptr]);
            active[pos] = 1;
            parent[pos] = pos;
            sz[pos] = 1;
            compMax[pos] = B[pos];
            cur += B[pos];

            if (pos > 0 && active[pos - 1]) unite(pos, pos - 1);
            if (pos + 1 < N && active[pos + 1]) unite(pos, pos + 1);

            ptr++;
        }
        ans[qi] = cur;
    }

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

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.