Lycanthropy
题目背景
小正方形亲眼看见了自己昔日的朋友被卷进了黑暗的深渊,然而它无力阻止……
现在它的朋友已经向它发起了攻击,因此小正方形不得不抵抗。
题目描述
我们把山顶上的湖泊看作一条长度为 $m$ 的直线,一开始水深都在水平线上,我们视作此时的水深为 '0'
接下来,在一瞬间,小正方形的"朋友"们跳起并扎入水中,导致在入水点的水降低而远离入水点的水升高,注意两个 "朋友" 可能在同一地点入水。
小正方形的每个朋友有一个体积数值 $v$,当体积为 $v$ 的一个朋友跳入水中,我们设入水点为 $i$,将会导致 $i - v + 1$ 到 $i$ 的水位依次降低 $1,2,\cdots,v$
同样地,第 $i$ 到 $i + v - 1$ 的水位会依次降低 $v,v - 1,\cdots,1$.
相对应地,$i - v$ 的水位不变, $i - v - 1$ 到 $i - 2 * v$ 水位依次增加 $1,2,\cdots,v$, $i - 2 * v$ 到 $i - 3 * v + 1$ 水位依次增加 $v,v - 1,\cdots,1$
同样,$i + v$ 水位不变,$i + v + 1$ 到 $i + 2 * v$ 水位增加 $1,2,\cdots,v$,$i + 2 * v$ 到 $i + 3 * v - 1$ 水位依次增加 $v,v - 1,\cdots,1$
现在小正方形想要穿过这个湖,他想要知道在这 $n$ 个"朋友"跳入水中后湖上每个节点的水位,你能帮帮它吗?
输入输出格式
输入格式
第一行为两个整数 $n$,$m$,表示"朋友"的数目与湖泊的宽度。
接下来 $n$ 行,一行两个整数 $v,x$,表示第 $i + 1$ 个朋友的体积与入水点。
输出格式
一行 $m$ 个整数,第 $i$ 个整数表示 $i$ 号位的水深。
输入输出样例
输入样例 #1
1 10
1 5
输出样例 #1
0 0 1 0 -1 0 1 0 0 0
输入样例 #2
2 10
2 6
3 1
输出样例 #2
-2 0 0 0 0 0 2 2 2 2
说明
对于 $30\%$ 的数据,$n <= 50,m <= 500$
对于 $70\%$ 的数据,$n <= 10^5,m <= 10^5$
对于 $100\%$ 的数据,$n <= 10^6,m <= 10^6,1 <= v <= 10000,1 <= x <= m$