Somen Nagashi

题目描述

共有 $N$$$ 人参加一个名为 Flowing Noodles 的活动。人们排成一列，从前到后依次编号为 $1$ 到 $N$。 在活动中，下面的事件发生了 $M$ 次：

在时间 $T_i$，数量为 $W_i$ 的面被放下。排在队首的人得到全部面（如果队列中无人，则无人得到）。该人随后离开队列，并在时间 $T_i+S_i$ 回到他们在队列中的原始位置。

在时间 $X$ 回到队列中的人被视为在时间 $X$ 时在队列中。 在所有 $M$ 次事件结束后，报告每个人获得的面条总量。

输入格式

输入按照标准输入给出，格式如下： $N$ $M$ $T_1$ $W_1$ $S_1$ $\vdots$ $T_M$ $W_M$ $S_M$

输出格式

输出 $N$ 行。 第 $i$ 行应包含第 $i$ 人获得的面条数量。

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

101
10
1000

3 1
1 1 1

1
0
0

1 8
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8

15

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq M \leq 2\times 10^5$ 0 <T_1 <\ldots < T_M \leq 10^9 $1 \leq S_i \leq 10^9$ $1 \leq W_i \leq 10^9$ 所有输入值均为整数。事件按如下进行：

在时间 $1$，数量为 $1$ 的面被放下。人 $1$、$2$ 和 $3$ 在队列中，队首的人，即人 $1$，得到面并离开队列。 在时间 $2$，数量为 $10$ 的面被放下。人 $2$ 和 $3$ 在队列中，队首的人，即人 $2$，得到面并离开队列。 在时间 $4$，人 $1$ 回到队列。 在时间 $4$，数量为 $100$ 的面被放下。人 $1$ 和 $3$ 在队列中，队首的人，即人 $1$，得到面并离开队列。 在时间 $10$，数量为 $1000$ 的面被放下。只有人 $3$ 在队列中，队首的人，即人 $3$，得到面并离开队列。 在时间 $100$，数量为 $1000000000$ 的面被放下。队列中无人，因此无人得到这些面。 在时间 $102$，人 $2$ 回到队列。 在时间 $10004$，人 $1$ 回到队列。 在时间 $1000000010$，人 $3$ 回到队列。

人 $1$、$2$、$3$ 分别获得的面条总量为 $101$、$10$ 和 $1000$。

标签: AtCoder|abc320E

来源

AtCoder|abc320E