问题陈述
很棒的输送机 (ACM)是工厂最重要的设备 工业输送机产品公司 (ICPC)。 ACM 有一条很长的传送带,可以将他们的产品从一些点运送到其他点。您是一名程序员,受雇为产品交付制定高效的日程计划。
ACM 的传送带以相等的间隔经过 $N$ 个点。传送带上有多个板,每个板上最多可以放置一件产品。最初,任何点都没有车牌。输送带单位时间内恰好移动一个板的长度;一秒后,位置 1 上有一块板,而其他位置上没有板。再过 1 秒后,位置 1 的板移动到位置 2,新的板出现在位置 1,依此类推。请注意,传送带的盘子数量不受限制:在 $N$ 秒或更晚之后,每个 $N$ 位置恰好有一个盘子。
配送任务由位置$a$和$b$表示;通过将产品放在 $a$ 处的传送带上的盘子上,并在 $b-a$ 秒后 ($a < b$) 在 $b$ 取回产品来完成交付。 (当然,放置时的位置必须有空盘。)此外,放置和取出产品必须按以下方式进行:
- 放置和取出产品时,必须将板放置在该位置。也就是说,产品必须在整数秒内放入和检索。
- 在同一位置放置和取出 不能 同时完成。另一方面,在不同位置的放置和取出可以同时进行。
如果有多个任务,则可以通过在将每个产品放到传送带上时更改计划来减少完成所有任务的时间。你的工作是编写一个程序,最大限度地减少完成所有任务的时间……等等,等等。你什么时候开始误以为你一开始就能知道所有的任务?新的交货请求不断涌现,就像传送带上的盘子一样!因此,您应该根据每个新请求更新您的最佳时间表。
请求由起点 $a$、目标点 $b$ 以及从 $a$ 交付到 $b$ 的产品数量 $p$ 组成。交货请求将添加 $Q$ 次。你的(真正的)工作是编写一个程序,使得对于每个 $1 \le i \le Q$,最小化完成请求 1 到 $i$ 中的交付任务的整个时间。
输入
输入由单个测试用例组成,格式如下。
$N$ $Q$ $a_{1}$ $b_{1}$ $p_{1}$ $\vdots$ $a_{Q}$ $b_{Q}$ $p_{Q}$
第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 10^5$, $1 \le Q \le 10^5$):$N$ 是传送带经过的位置数,$Q$ 是将到来的请求数。 以下$Q$行中的第$i$行由三个整数$a_{i}$、$b_{i}$和$p_{i}$组成($1 \le a_{i} < b_{i} \le N$, $1 \le p_{i} \le 10^9$),这意味着第$i$请求需要将$p_{i}$产品从位置$a_{i}$交付到位置$b_{i}$。
输出
在第 $i$ 行中,打印完成请求 $1$ 到 $i$ 所需的所有任务的最短时间。
示例输入 1
5 2 1 4 1 2 3 1
样本输入 1 的输出
4 4
示例输入 2
5 2 1 4 1 2 3 5
样本输入 2 的输出
4 8
示例输入 3
5 2 1 3 3 3 5 1
样本输入 3 的输出
5 6
示例输入 4
10 4 3 5 2 5 7 5 8 9 2 1 7 5
样本输入 4 的输出
6 11 11 16
注意
对于第一个示例,仅完成第一个请求的最短时间为 $4$ 秒。所有两个请求也可以在 4 美元秒内完成。见下图。