Mooclear Reactor 2

Research check: the official Codeforces problem page and the official Codeforces Round 1084 editorial point to the same intended idea: fix the final set size, sweep the reactivity threshold downward, and maintain top energies. The editorial page currently exposes hints/code more than prose, so the proof here is written from the supplied statement, which is the canonical source.

Let a chosen set contain $s$ particles. Every chosen particle must tolerate the other $s-1$ particles, so the condition is

$y_i >= s-1$ for every chosen particle $i$.

That is the main simplification. The reactor is basically a top-$K$ problem wearing a physics hat.

First solve the original particles only. Let $k=s-1$, and define

$E_k = \{i : y_i >= k\}$.

For this threshold, any subset of at most $k+1$ particles from $E_k$ is valid, because each selected particle has at most $k$ others. Since all energies are positive, the best such subset is the largest up to $k+1$ values of $x$ inside $E_k$. Let

$B[k] =$ sum of the largest up to $k+1$ energies among originals with $y_i >= k$.

Then the best answer without using any shop particle is

$base = max B[k]$ over $0 <= k <= n$.

Now handle a query particle $(x,y)$. If Bessie buys it but does not use it, the answer is still $base$. If she does use it with $r$ original particles, then the shop particle sees $r$ other particles, so $r <= y$. Also, each chosen original sees the shop particle plus the other $r-1$ originals, so each needs $y_i >= r$.

So for a fixed $r$, the best partner sum is the largest up to $r$ original energies among particles with $y_i >= r$. Define

$C[k] =$ sum of the largest up to $k$ energies among originals with $y_i >= k$.

Then the best query answer that uses the shop particle is

$x + max(C[0], C[1], ..., C[y])$.

Precompute the prefix maximum array $P[y] = max_{0 <= k <= y} C[k]$, and each query becomes

$max(base, x + P[y])$.

Why does using up to $k$ instead of exactly $k$ not cheat? If $C[k]$ uses only $l <= k$ originals, then those originals all have $y_i >= k >= l$, and a shop particle with $y >= k$ also tolerates $l$ originals. So that subset is valid. Conversely, any valid query subset with $r$ originals is bounded by $C[r]$. No fake energy sneaks in.

To compute $B[k]$ and $C[k]$, sort original particles by decreasing $y$. Sweep $k$ from $n$ down to $0$, inserting all particles that become eligible, meaning all particles with $y_i >= k$. Maintain a min-heap containing the largest up to $k+1$ inserted energies and a running sum cur.

After inserting newly eligible particles, pop the smallest kept energy while the heap size exceeds $k+1$. This is safe because the capacity only decreases as $k$ goes down; once a value is too small to be kept, it will never become useful later. Future particles only add more competition. Brutal, but fair.

At threshold $k$:

• cur is $B[k]$, the sum of the largest up to $k+1$ eligible energies, so update base.
• $C[k]$ is the largest up to $k$ eligible energies. Since the heap stores up to $k+1$, this is cur if the heap size is at most $k$, otherwise cur - heap.top().

Edge cases:

• $y=0$ query: the bought particle can only be used alone, so $P[0]=0$ and the candidate is just $x$.
• $y=n$ query: the bought particle may be used with all $n$ originals, but only originals with $y_i >= n$ can survive that. The sweep includes $k=n$, so no off-by-one nonsense.
• Bessie may ignore the bought particle, so always take max(base, ...).

Complexity per test case is $O(n log n + m)$ after sorting and heap operations, with $O(n)$ memory. Across all tests this fits because total $n$ and total $m$ are at most $2 * 10^5$.

Research used: official problem statement and official Codeforces editorial.