P17086 [COTS 2026] Clouds / Oblaci (No testdata yet)

2s, 512M

There are $N$ clouds in the sky. Clouds are different: the $i$-th cloud is described by three integers $t_i, l_i,$ and $v_i$, which represent its arrival time, length, and speed. At time $t_i$, the $i$-th cloud covers the interval $[-l_i, 0]$. After that, it keeps moving to the right at a constant speed of $v_i$ per second. In other words, at time $s \ge t_i$, the interval covered by the $i$-th cloud is $[v_i(s - t_i) - l_i, v_i(s - t_i)]$. For each integer $x$ satisfying $0 \le x \le M$, determine the total number of seconds during which point $x$ is covered by at least one cloud.

The first line contains positive integers $N$ and $M$ ($1 \le N \le 5\,000$, $1 \le M \le 10^6$), representing the number of clouds and the maximum coordinate we are interested in. Each of the next $N$ lines contains three integers $t_i$, $l_i$, and $v_i$ ($0 \le t_i \le 10^6$, $1 \le l_i \le 10^6$, $1 \le v_i \le 2$), describing the $i$-th cloud.

Output $M + 1$ numbers: for each point $0, 1, \dots, M$ in order, output the total time (in seconds) during which that point is covered by at least one cloud.

### Sample Explanation Below is the explanation for sample $1$. The first cloud covers point $0$ from time $0$ to time $3$. The second cloud reaches this point at time $4$ and passes it at time $6.5$. The third cloud reaches this point at time $5$ and passes it at time $9$. Overall, point $0$ is covered for $8$ seconds. ### Subtasks | Subtask | Score | Constraints | | :---: | :---: | :--- | | $1$ | $16$ | $M, t_i, l_i \le 5\,000$ | | $2$ | $12$ | For every cloud $i$, $v_i = 1$. | | $3$ | $37$ | $N \le 10$ and $M, t_i, l_i \le 10^5$ | | $4$ | $35$ | No additional constraints. | Translated by ChatGPT 5