P7405 [JOI 2021 Final] Snowball / Snowball

On an infinitely long number line, there are $N$ snowballs, numbered $1 \sim N$. The $i$-th snowball is at point $A_i$. At the beginning, the entire number line is fully covered with snow. Then, over the next $Q$ days, strong winds will blow. The wind strength on day $j$ is $W_j$. If $W_j$ is positive, all snowballs move to the right by $W_j$ units. If $W_j$ is negative, all snowballs move to the left by $-W_j$ units. When an interval $[a,a+1]$ is covered with snow, a snowball’s mass increases by $1$ when it rolls over that interval, and the snow in that interval is cleared. Initially, every snowball has mass $0$, and during these $Q$ days, no new snow falls. You want to know the mass of each snowball after these $Q$ days end.

The first line contains two integers $N, Q$, representing the number of snowballs and the number of days with wind. The second line contains $N$ integers $A_i$, representing the initial positions of the $N$ snowballs. The next $Q$ lines each contain one integer $W_j$, representing the wind strength of each day.

Output $N$ lines, each containing one integer, representing the mass of each snowball after the $Q$ days.

#### Explanation of Sample 1 The initial positions of the snowballs are $-2, 3, 5, 8$, and the initial masses are $0, 0, 0, 0$. - After the first day, the snowballs are at positions $0, 5, 7, 10$, with masses $2, 2, 2, 2$. - After the second day, the snowballs are at positions $-4, 1, 3, 6$, with masses $4, 4, 2, 3$. - After the third day, the snowballs are at positions $3, 8, 10, 13$, with masses $5, 4, 2, 6$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (33 pts): $N, Q \le 2000$. - Subtask 2 (67 pts): no special restrictions. For $100\%$ of the testdata, $1 \le N, Q \le 2 \times 10^5$, $|A_i|, |W_j| \le 10^{12}$, $A_i < A_{i+1}$. #### Note Translated from [The 20th Japanese Olympiad in Informatics Final Round B English translation Snowball](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t2-en.pdf). Translated by ChatGPT 5