1935. A Total Made of Numbers That Expire

Numbers are added to a running total, and each one leaves again on its own schedule. Three operations arrive, one per line:

add t x d at time t, add x to the total for d units of time sum t at time t, print the total of the contributions still live count t at time t, print how many contributions are still live

7 add 1 10 5 -> 10 counts from time 1 to time 5 add 2 7 2 -> 7 counts from time 2 to time 3 sum 2 -> 17 sum 4 -> 10 the 7 left at time 4 count 4 -> 1 add 4 3 9 -> 3 counts from time 4 to time 12 sum 6 -> 3 the 10 left at time 6

## The rules, stated so the answer is decidable

• add prints nothing. sum and count each print one line.
• A contribution added at time t with duration d counts for every time
• now with t <= now < t + d, and no longer counts at now = t + d.
• Contributions are independent. Two adds of the same amount at the same time
• are two contributions, both counted, both expiring separately.
• x may be 0. A contribution of zero still counts towards count while it is
• live, because count counts contributions rather than value.
• sum of nothing live is 0.
• The times across the input never decrease.
• d is at least 1, so nothing expires before it has counted.

Problem 1913 counts hits in a fixed five minute window. Because every hit there has the same lifetime, the oldest hit is always the next one to go, and a plain queue is enough. Here each contribution brings its own duration, so the order they leave in is NOT the order they arrived in, and a queue gives wrong answers rather than slow ones.

## What most people try first

Keep the list of everything ever added and total the live ones on each query. Correct, and O(n) per query. With q at 2 * 10^5 and a query every other line, that is about 10^10 additions.

The next thought, if problem 1913 is fresh in mind, is a queue in arrival order, retiring from the front while the front has expired. That is fast and it is wrong: a contribution with a long duration sitting at the front BLOCKS the retirement of short ones behind it that have already expired, so the total stays too high. Worse, the front may expire while something behind it has not, and then retiring from the front is right by accident, which means a small test can easily miss the bug.

## A min-heap on the death time, with a running total

deaths a min-heap of (death time, amount) total the sum of the live amounts count how many are live

At the start of every operation, at its stated time now, pop the heap while its smallest death time is <= now, subtracting each popped amount from total and one from count. Then add pushes (now + d, x) and adds to both, while sum and count are single reads.

## Why it is correct

The purge is exact because the clock never decreases: a contribution whose death time has passed can never become live again, so removing it can never be premature, and the heap hands them over in death order so no expired contribution can hide behind a live one. That last clause is precisely what the queue gets wrong.

Nothing is ever rewritten here, unlike problems 1932 and 1933, so no entry in this heap can become stale and no staleness test is needed. Every pair pushed is eventually popped exactly once, and total is maintained by one addition and one subtraction per contribution rather than recomputed, so it is always the sum of exactly the pairs still in the heap.

## Why it is fast

Each add pushes one pair and each pair is popped once, so the purge loop runs at most q times across the whole run. Every operation is amortised O(log q), and sum and count are O(1) after the purge.

## Overflow

A single x is at most 10^9, which fits in a signed 32 bit integer, whose limit is 2147483647. The TOTAL does not. With 2 * 10^5 contributions of 10^9 all live at once, the total reaches 2 * 10^14, so total must be a 64 bit integer. In JavaScript 2 * 10^14 is still exact as a plain number, since it is well under 2^53, so no BigInt is needed, but a bitwise operator would truncate to 32 bits and must not be used on it. A death time is t + d and reaches 2 * 10^9, which fits but with little room, so 64 bit is the safer choice there too.

## Cost

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

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ t ≤ 1000000000`, and the times across the input never decrease - `0 ≤ x ≤ 1000000000` - `1 ≤ d ≤ 1000000000` - the total starts at 0 with nothing live - each operation must run in amortised `O(log q)`, so the whole run is `O(q log q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so totalling the live contributions on every query passes them while doing about `10^10` additions at `q = 200000`