OutOfMemoryError

The main thing to notice is that a crash does not partially undo anything. It nukes the entire current history and restores the original array.

So at any moment, the only operations that matter are the operations since the most recent crash. Call that current block a segment.

For an index $x$, during the current segment its value is

$$A_x = a_x + \sum_{i \text{ in current segment},\ b_i=x} c_i.$$

Since every $c_i \ge 0$, values never decrease inside a segment. Also, each operation changes exactly one element, so after applying operation $(b_i,c_i)$, the only element that could newly become greater than $h$ is $b_i$. No need to scan the whole array. Scanning would be silly. Resetting the whole array every crash would be worse: that is how you manufacture your own TLE.

The direct simulation idea is:

1. Apply the update to position $b_i$.
2. If that position becomes greater than $h$, a crash happens.
3. After a crash, all values return to the original array.

The only annoying part is step 3. There may be $O(m)$ crashes, and resetting all $n$ elements each time would be $O(nm)$ in the worst case.

Instead, use a lazy reset.

Maintain:

• orig[i]: the original value $a_i$.
• cur[i]: the currently stored value for index $i$.
• seen[i]: the segment/version where cur[i] is valid.
• ver: the current segment number.

Initially ver = 1. Before using index $x$, check whether seen[x] == ver.

If not, then cur[x] belongs to an old segment and is garbage for the current one. Reinitialize it lazily:

$$cur[x] = orig[x].$$

Then set seen[x] = ver.

Now process the update:

$$cur[x] \leftarrow cur[x] + c_i.$$

If cur[x] > h, the computer crashes. We do not reset arrays manually. We simply increment ver. From now on, every old cur[i] automatically becomes stale because its seen[i] is from an older version.

At the end, the final value of index $i$ is:

• cur[i] if seen[i] == ver, because it was touched in the final segment;
• otherwise orig[i], because it has not been changed since the last crash.

Why this works:

The invariant is that for every index $i$ with seen[i] == ver, cur[i] equals the actual value of $i$ in the current segment. For every other index, the actual value is just orig[i], because it has not been initialized or touched since the latest crash.

Before an update, we lazily restore the target index if needed, so the invariant holds for that index. Then we add $c_i$, matching the operation exactly. If the result is at most $h$, no crash happens and the invariant continues to hold.

If the result is greater than $h$, a crash resets every element to orig. Incrementing ver makes all previously stored values stale at once, which is exactly equivalent to resetting the whole array, except we spend $O(1)$ instead of doing the clown-car $O(n)$ reset.

Edge cases:

• If $c_i=0$, nothing special happens.
• If the original value already equals $h$, any positive update to that index crashes.
• If every operation crashes, ver just keeps increasing and the final output is the original array.
• Large accumulated values require long long, because sums can reach about $2\cdot 10^{14}$.

Complexity per test case is

$$O(n+m)$$

time and

$$O(n)$$

memory. Across all test cases, this fits easily because the total $n$ and total $m$ are bounded by $2\cdot 10^5$.