P17086 [COTS 2026] 云朵 / Oblaci（暂无数据）

2s, 512M

天空中共有 $N$ 朵云。云朵之间亦有分别，第 $i$ 朵云由三个整数 $t_i, l_i$ 和 $v_i$ 描述，分别代表它的到达时间、长度和速度。 在时刻 $t_i$，第 $i$ 朵云覆盖了区间 $[-l_i, 0]$。在那之后，它以每秒 $v_i$ 的恒定速度不断向右移动。换句话说，在时刻 $s \ge t_i$，第 $i$ 朵云覆盖的区间为 $[v_i(s - t_i) - l_i, v_i(s - t_i)]$。 对于满足 $0 \le x \le M$ 的每一个整数 $x$，请确定点 $x$ 至少被一朵云覆盖的总秒数。

第一行包含正整数 $N$ 和 $M$（$1 \le N \le 5\,000$，$1 \le M \le 10^6$），分别表示云朵的数量和我们感兴趣的最大坐标点。 接下来的 $N$ 行中，第 $i$ 行包含三个整数 $t_i$, $l_i$ 和 $v_i$（$0 \le t_i \le 10^6$，$1 \le l_i \le 10^6$，$1 \le v_i \le 2$），即第 $i$ 朵云的描述。

输出 $M + 1$ 个数字：依次对应每个点 $0, 1, \dots , M$，该点至少被一朵云覆盖的总时间（以秒为单位）。

### 样例解释 以下为样例 $1$ 解释。 第一朵云在时刻 $0$ 到时刻 $3$ 之间覆盖了点 $0$。第二朵云在时刻 $4$ 到达该点，并在时刻 $6.5$ 通过该点。第三朵云在时刻 $ 5 $ 到达该点，并在时刻 $ 9 $ 通过该点。总的来说，点 $ 0 $ 被覆盖了 $ 8 $ 秒。 ### 子任务 | 子任务 | 分数 | 限制 | | :---: | :---: | :--- | | $1$ | $16$ | $M, t_i, l_i \le 5\,000$ | | $2$ | $12$ | 对于每朵云 $i$，有 $v_i = 1$。 | | $3$ | $37$ | $N \le 10$ 且 $M, t_i, l_i \le 10^5$ | | $4$ | $35$ | 没有额外限制。 |