1924. A Stack That Can Also Remove Its Largest Value

Build a stack that answers five operations, one per line:

push v put v on top, printing nothing pop remove the top value and print it top print the top value without removing it peekmax print the largest value currently held popmax remove the largest value, wherever it sits, and print it

8 push 5 -> push 1 -> push 5 -> peekmax -> 5 popmax -> 5 the UPPER 5 leaves, so the stack is now 5 1 top -> 1 popmax -> 5 pop -> 1

## The rules, stated so the answer is decidable

• push prints nothing. The other four each print exactly one line.
• pop, top, peekmax and popmax on an empty stack print empty and
• change nothing.
• If several entries share the largest value, popmax removes the one CLOSEST
• TO THE TOP. Removing the bottom-most copy instead gives a different stack and
• therefore different later output, so the tie rule is part of the answer.
• popmax removes an entry from the middle. The entries above it keep their
• order and close the gap, so a later pop returns what was above the removed
• entry.

Problem 164 is this stack without popmax: it only has to REPORT an extreme, which one parallel stack of running minima settles. Removing the extreme is what breaks that parallel stack, because a deletion in the middle invalidates every running extreme recorded above it. That is the whole difficulty here.

## What most people try first

Keep the values in one array and scan it on every peekmax and popmax. That is correct and it is O(n) per query. With q at 2 * 10^5 and a stream that is mostly peekmax, that is about 2 * 10^10 comparisons.

The second thing people try is the parallel running-maximum stack from problem 164. It answers peekmax in constant time and then gives a wrong answer the first time popmax takes something from the middle, because every running maximum recorded above the hole was computed with the removed value in it.

## Two orders at once, with lazy deletion

Keep the stack in an array that is never compacted, plus a flag per slot saying whether that entry is still live:

vals[1..m] every value ever pushed, in push order dead[1..m] whether that slot has been removed tp the index the top is at or below heap a max-heap of (value, index), biggest value then biggest index

push appends, sets tp to the new slot and pushes onto the heap. peekmax and popmax discard heap entries whose slot is already dead until the root is live. pop and top walk tp down past dead slots.

## Why it is correct, and why it is fast

Correctness: the heap orders by value then by index, so its live root is the largest value and, among equal values, the one pushed latest, which is the one nearest the top. The array keeps push order untouched, so skipping dead slots from tp downwards visits exactly the live entries in stack order.

Cost: every slot is marked dead at most once, so tp moves down at most m times in the whole run and the heap discards at most m stale roots in the whole run. Those two loops therefore contribute O(q) across the run, not per operation. Each heap push and pop is O(log q). So push, pop and top are amortised O(1) and peekmax and popmax are O(log q) amortised.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. Nothing is summed here, so no accumulator can grow past a single value and 32 bit arithmetic is safe for the values themselves. The slot index reaches 2 * 10^5, also small. If you pack value and index into one key to sort the heap by, note that 10^9 * 2 * 10^5 is 2 * 10^14 and needs 64 bits, which is why the implementation above compares the two fields instead.

## Cost

O(q log q) in total, with memory proportional to the number of pushes.

Constraints - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - the stack starts empty - `push`, `pop` and `top` must run in amortised `O(1)` - `peekmax` and `popmax` must run in amortised `O(log q)` - the judge cannot enforce those bounds: the declared tests are small and there is no test generator yet, so a scanning solution will pass them. The contract is the exercise, and at `q = 200000` with every operation a `peekmax` a scan does about `2 * 10^10` comparisons