409963: GYM103870 H Zero Trust

This statement is entirely fictional and no such events will ever come to happen in real life. Since in accordance with popular belief, Waymo is in fact broke.

Waymo has decided to make the class he is TA'ing for solve Lattice MST (from the Teamscode Summer 2021 contest). To help keep the students motivated to solve the problem, he will buy each student a cup of milk tea (with aloe vera instead of boba since aloe vera $$$>$$$ boba). However, Waymo does not feel the obligation to buy milk tea for someone with zero trust. Trust is calculated as follows:

Every student $$$i$$$ starts of with $$$t_i$$$ trust. Then over the course of $$$Q$$$ days, if by day $$$d$$$, a student has not solved Lattice MST, their trust will decrease by $$$x_d$$$. Note that similar to real life, milk tea is bought before trust decreases. Also, note that trust is never negative. If a person ever has negative trust, their trust is set back to $$$0$$$.

So over the course of the $$$Q$$$ days, you have to output how many cups of milk tea Waymo has to buy on each day as well as the sum of trusts over all students. Assume that none of the students can solve Lattice MST.

The first line contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 2 \cdot 10^5)$$$, the number of students and the number of days.

The second line contains $$$N$$$ integers, where the $$$i$$$'th integer is $$$t_i$$$ $$$(0 \leq t_i \leq 10^9)$$$, the initial trust of the $$$i$$$'th student.

In the following $$$Q$$$ lines, each line contains one integer $$$x_i$$$ $$$(0 \leq x_i \leq 10^9)$$$, denoting the amount of trust lost if a student does not finish by the end of day $$$i$$$.

Output $$$Q$$$ lines containing $$$2$$$ integers per line, where the first integer on a line is the number of cups of milk tea Waymo has to buy and the second integer is the sum of trusts over all students.

6 5
10 0 3 3 6 6
2
0
3
3366
1

5 28
5 18
5 18
3 7
0 0

Remember that milk tea is bought before trust is lost.

The "trust table" for each day is as follows:

Day $$$1$$$: $$$[10, 0, 3, 3, 6, 6]$$$

Day $$$2$$$: $$$[8, 0, 1, 1, 4, 4]$$$

Day $$$3$$$: $$$[8, 0, 1, 1, 4, 4]$$$

Day $$$4$$$: $$$[5, 0, 0, 0, 1, 1]$$$

Day $$$5$$$: $$$[0, 0, 0, 0, 0, 0]$$$

Note that the last trust loss of $$$1$$$ does not actually matter at all.

—

Idea: 3366

Preparation: 3366

Occurrences: Novice 9, Intermediate 8, Advanced 3