Overview

For each threshold value \(K\), products with \(A_i < K\) are considered “defective,” and we need to compute the sum of the maximum weights across each contiguous segment of defective products.

We process the queries in ascending order of \(K\), adding products that become defective one by one, and manage the contiguous segments using Union-Find.

Analysis

First, let’s consider a fixed threshold value \(K\).

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

For example, suppose the defective positions look like this:

Defective Defective Good Defective Defective Defective Good Defective

Then the contiguous segments of defective products are:

[1,2], [4,6], [8,8]

For each contiguous segment, we could further split it into multiple boxes, but there is no benefit in doing so.

This is because if the maximum weight of a segment is \(M\), placing the entire segment in one box costs \(M\) in shipping.
On the other hand, splitting into multiple boxes results in the sum of each box’s maximum weight, which is at least \(M\).

Therefore, the optimal strategy is:

Place each contiguous segment of defective products into a single box.

Thus, the answer is:

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

---

A naive approach would examine all products for each query to find contiguous segments of defective products.
However, this takes \(O(NQ)\) time, which is too slow for \(N+Q \leq 2 \times 10^5\).

Instead, we process queries in ascending order of threshold \(K\).

As \(K\) increases, the set of products satisfying \(A_i < K\) only grows and never shrinks.
This means we can handle all queries by only “adding” defective products.

When adding a newly defective position, if a neighboring position is already defective, the contiguous segments merge.
Union-Find is well-suited for managing these contiguous segments.

Algorithm

First, sort the products in ascending order of \(A_i\).
Also, sort the queries in ascending order of \(K_j\).

For the current threshold \(K\) being processed, we add all not-yet-added products satisfying:

\[ A_i < K \]

Added products are treated as “active,” i.e., defective.

In the Union-Find, adjacent active positions are managed as the same contiguous segment.

For each contiguous segment, we maintain the maximum weight within that segment.
We keep a running total total such that:

\[ \text{total} = \sum \text{maximum weight of each contiguous segment} \]

---

Consider the changes when adding product \(x\).

First, a new contiguous segment consisting of just position \(x\) is created, so:

\[ \text{total} += B_x \]

Next, if the left neighbor \(x-1\) is already defective, they become the same contiguous segment.
Let \(m_1, m_2\) be the maximum weights of the two segments. Before merging, their contribution is:

\[ m_1 + m_2 \]

After merging, the contribution is:

\[ \max(m_1, m_2) \]

Therefore, the decrease in total is:

\[ m_1 + m_2 - \max(m_1, m_2) = \min(m_1, m_2) \]

In other words, when merging two contiguous segments, we subtract the smaller maximum weight from total.

The right neighbor \(x+1\) is handled similarly.

---

Let’s look at a concrete example.

Position:  1  2  3  4
B:         5  2  7  3

Suppose positions \(1\) and \(3\) are currently defective.

Defective Good Defective Good

The contiguous segments are \([1]\) and \([3]\), so:

\[ \text{total} = 5 + 7 = 12 \]

Now position \(2\) becomes defective:

Defective Defective Defective Good

First, we add position \(2\) as a standalone segment:

\[ \text{total} = 12 + 2 = 14 \]

Merge with the left segment \([1]\).
The maximum weights are \(5\) and \(2\), so we subtract the smaller one, \(2\):

\[ \text{total} = 14 - 2 = 12 \]

Next, merge with the right segment \([3]\).
The current left segment \([1,2]\) has maximum weight \(5\), and the right segment \([3]\) has maximum weight \(7\).
We subtract the smaller one, \(5\):

\[ \text{total} = 12 - 5 = 7 \]

The final contiguous segment is \([1,2,3]\) with maximum weight \(7\), which is correct.

---

The processing flow is as follows:

1. Sort products \((A_i, i)\) in ascending order of \(A_i\)
2. Sort queries \((K_j, j)\) in ascending order of \(K_j\)
3. Start with total = 0
4. For each query \(K\), add all not-yet-added products with \(A_i < K\)
5. When adding, merge with left and right active positions using Union-Find
6. The current total is the answer for that query
7. Since queries were processed in sorted order, restore the original order for output

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\)
  • Sorting products 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, we maintain the following for each connected component:

• parent: parent node
• size: size for union by size
• comp_max: maximum \(B_i\) value within that connected component

We also use active to track whether a position has already been added as defective.

active[x] = 1

After setting this, we check the left and right neighbors:

if x > 0 and active[x - 1]:
    total -= unite(x, x - 1)

if x + 1 < N and active[x + 1]:
    total -= unite(x, x + 1)

unite(x, y) merges two connected components and returns the value to subtract from total, namely:

\[ \min(\text{max weight of left component}, \text{max weight of right component}) \]

An important note: the condition for being defective is:

\[ A_i < K \]

It is not \(A_i \leq K\).
Therefore, the addition condition during query processing is:

while ip < N and items[ip][0] < k:

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, Q = data[0], data[1]

    B = [0] * N
    items = [None] * N
    p = 2
    for i in range(N):
        a = data[p]
        b = data[p + 1]
        p += 2
        B[i] = b
        items[i] = (a, i)

    queries = [(data[p + i], i) for i in range(Q)]

    items.sort()
    queries.sort()

    parent = list(range(N))
    size = [1] * N
    comp_max = B[:]
    active = bytearray(N)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def unite(x, y):
        rx = find(x)
        ry = find(y)
        if rx == ry:
            return 0
        if size[rx] < size[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        size[rx] += size[ry]
        mx = comp_max[rx]
        my = comp_max[ry]
        if my > mx:
            comp_max[rx] = my
            return mx
        else:
            return my

    ans = [0] * Q
    total = 0
    ip = 0

    for k, qi in queries:
        while ip < N and items[ip][0] < k:
            x = items[ip][1]
            active[x] = 1
            total += B[x]

            if x > 0 and active[x - 1]:
                total -= unite(x, x - 1)
            if x + 1 < N and active[x + 1]:
                total -= unite(x, x + 1)

            ip += 1

        ans[qi] = total

    print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.