1944. Walking A Stream Too Long To Expand

A stream is given in run length encoded form: n runs, each a value and a count, meaning that value repeated that many times. The runs appear in stream order. Build a cursor over the stream it describes.

next print the next value and consume it peek print the next value without consuming it skip x discard the next x values and print how many were ACTUALLY discarded, which is fewer than x when the stream runs out first remaining print how many values are still unconsumed

next and peek print done when the stream is exhausted.

## The constraint that decides the whole design

A single count reaches 10^18, and so does the total. The expanded stream can therefore never be built: writing it out would need a billion gigabytes. Every operation has to be answered from the runs themselves.

That is also why skip reports what it achieved rather than what it was asked for. A skip of 10^18 on a stream of length 5 must say 5, and the difference between those two numbers is the whole question.

## What most people try first

Expand the runs into an array and index it. On the small samples it works perfectly, which is the trap: the design is not slightly too slow, it is impossible at the stated scale, and no amount of tuning rescues it.

The second attempt keeps the stream compressed but implements skip x by stepping one value at a time. That is correct and it is O(x), so a single skip of 10^18 never finishes.

## A cursor of two numbers

Hold which run the cursor is in, and how far into that run it has got.

``` ri index of the current run off how many values of run ri have been consumed, 0 <= off < CNT[ri]

next: the value is VALU[ri]; off goes up by one, and when off reaches CNT[ri] the cursor moves to the next run and off resets to 0 skip x: repeatedly consume whole remainders of runs room = CNT[ri] - off what is left of this run take = min(room, x - moved) what this step can use until x values are moved or the stream ends remaining: total - consumed, both held as counters ```

``` runs: (5, 3) (7, 2) the stream is 5 5 5 7 7, total 5

next -> 5 ri=0 off=1 remaining -> 4 skip 3 -> 3 crosses the run boundary: 2 from run 0, then 1 from run 1 next -> 7 ri=1 off=2 remaining -> 0 skip 9 -> 0 nothing is left, so the achieved skip is 0 next -> done ```

## Why it is correct

A skip advances by whole run remainders, and each step either exhausts the current run or finishes the skip, because take is the smaller of the two. So after each step either ri has increased or moved has reached x. Since ri can only increase n times in total across the entire run of the program, and each operation finishes when moved reaches x, the total work over all skips is O(n + q), not O(x) per skip. The amortised argument is the point: one skip may cross many runs, but all of the skips together cannot cross more run boundaries than there are runs.

remaining is a subtraction of two counters rather than a walk, so it is constant time whatever the cursor has done.

## The boundary that breaks a careless implementation

Skipping with an if rather than a while. The skip then stops at the first run boundary it meets and reports a number smaller than the truth, which is invisible on any test whose skip stays inside one run.

The other one is the clamp. Reporting x rather than what was achieved looks right until a skip runs off the end, and it also leaves the cursor past the end of the stream, so every later remaining is negative.

## Overflow

A count reaches 10^18 and so does the total, which does NOT fit in a signed 32 bit integer, whose largest value is 2147483647. Every count, position and total must be 64 bit, where the limit is about 9.2 * 10^18. Since the total is bounded by 10^18 and nothing here multiplies two of them, 64 bit is enough, but the intermediate total - done must also be 64 bit and must not be computed before done is clamped.

JavaScript is the one language that needs more than its default. A Number is exact only below 2^53, about 9.0 * 10^15, so a count near 10^18 is silently rounded; the reference solution uses BigInt, and no bitwise operator appears in it, since any one of them would truncate the value to 32 bits.

## Cost

O(1) for next, peek and remaining, and O(1) amortised for skip, so the whole run is O(n + q). The judge cannot enforce it: the declared tests are small and there is no test generator yet, so stepping one value at a time inside skip passes them all while never finishing a skip of 10^18.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 200000` - `0 ≤` each value `≤ 1000000000` - `1 ≤` each count, and the total of all counts is at most `1000000000000000000` - `0 ≤ x ≤ 1000000000000000000` - every operation runs in `O(1)`, amortised for `skip`, so the whole run is `O(n + q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so a skip that steps one value at a time passes them while never finishing a skip of `10^18`