Collection
This problem asks us to simulate receiving and losing coins of given values, and then calculating the total value.
The problem statement is horribly written, but N is the type of coin, and Q is the number of statements.
Since each statement can involve all N coins, if we do the problem naively, it takes 2*10^10 updates, which is too slow. We see the odd structure of the value of the coins, however, where V=N%10+1 This means that each tenth coin is the same. Given that, we can process each statement in 3 chunks:
- a -> next coin worth 1 >= a
- next coin -> last coin worth 10 <= b
- last coin -> b
The first and third bits take at most 10 updates each, and the middle section, since we know we're updating the same coin every loop of 10, we just divide the size of the range by 10, and take that quotient and apply it to each coin. Obviously for additions, we have to multiply this all by x.
This maxes any individual operation at 30 updates, or constant. This is plenty fast.