CF1804G Flow Control

Raj 有一条物理网络线路，将他的办公室连接到互联网。这条线路的带宽为 $b$ 字节每毫秒。 有 $n$ 个用户希望使用这条网络线路传输数据。第 $i$ 个用户将在第 $s_i$ 毫秒到第 $f_i$ 毫秒（包含两端）使用该线路。他的初始数据速率为 $d_i$。也就是说，在第 $s_i$ 毫秒时，他的数据速率为 $d_i$，之后会根据下述过程变化。 流量控制的过程如下。假设在第 $x$ 毫秒，有 $m$ 个用户试图通过该网络线路传输数据。记 $t_i$ 为这 $m$ 个用户中第 $i$ 个用户在该毫秒开始时的数据速率。所有 $t_i$ 都是非负整数。 1. 如果 $m = 0$，即该毫秒没有用户试图传输数据，则什么也不发生。 2. 如果所有 $t_i$ 的和小于等于 $b$，每个活跃用户都能成功完成本毫秒的传输（第 $i$ 个活跃用户传输了 $t_i$ 字节）。之后，每个活跃用户的数据速率增加 $1$，即每个 $t_i$ 增加 $1$。 3. 如果所有 $t_i$ 的和大于 $b$，则发生拥塞，本毫秒没有任何用户能成功传输数据。此时，每个 $t_i$ 都减半，即每个 $t_i$ 被替换为 $\lfloor \frac{t_i}{2} \rfloor$。 Raj 已知所有 $n$、$b$、$s_i$、$f_i$ 和 $d_i$ 的值，他想计算所有用户总共成功传输了多少字节的数据。

输入的第一行包含两个整数 $n$ 和 $b$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq b \leq 10^9$），分别表示将要使用该线路的用户数和线路带宽。 接下来的 $n$ 行，每行包含三个整数 $s_i$、$f_i$ 和 $d_i$（$1 \leq s_i \leq f_i \leq 10^9$，$1 \leq d_i \leq 10^9$），表示第 $i$ 个用户将在第 $s_i$ 到第 $f_i$ 毫秒（包含两端）尝试传输数据，且初始数据速率为 $d_i$。

输出一个整数，表示所有用户总共成功传输了多少字节的数据。

请参考第一个样例。 - 第 $1$ 毫秒：用户 $1$ 传输了 $2$ 字节。 - 第 $2$ 毫秒：用户 $1$ 传输了 $3$ 字节。 - 第 $3$ 毫秒：发生拥塞，没有用户传输数据。 - 第 $4$ 毫秒：用户 $1$ 传输了 $2$ 字节。 - 第 $5$ 毫秒：用户 $1$ 传输了 $3$ 字节。 在第二个样例中，从第 $7$ 毫秒到第 $11$ 毫秒，每毫秒都发生拥塞，唯一的用户每次都将速率减半。但在断开连接前，速率没有降到足够低。 请参考第三个样例。 - 第 $1$ 毫秒：用户 $1$ 传输了 $1$ 字节。 - 第 $2$ 毫秒：用户 $1$ 传输了 $2$ 字节。 - 第 $3$ 毫秒：用户 $1$ 传输了 $3$ 字节。 - 第 $4$ 毫秒：用户 $1$ 传输了 $4$ 字节。 - 第 $5$ 毫秒：用户 $1$ 传输了 $5$ 字节。 - 第 $6$ 毫秒：用户 $1$ 传输了 $6$ 字节。 - 第 $7$ 毫秒：发生拥塞，没有用户传输数据。 - 第 $8$ 毫秒：用户 $1$ 传输了 $3$ 字节，用户 $2$ 传输了 $3$ 字节。 - 第 $9$ 毫秒：发生拥塞，没有用户传输数据。 - 第 $10$ 毫秒：用户 $1$ 传输了 $2$ 字节，用户 $2$ 传输了 $2$ 字节。 - 第 $11$ 毫秒：用户 $1$ 传输了 $3$ 字节，用户 $2$ 传输了 $3$ 字节。 - 第 $12$ 毫秒：发生拥塞，没有用户传输数据。 - 第 $13$ 毫秒：用户 $2$ 传输了 $2$ 字节。 - 第 $14$ 毫秒：用户 $2$ 传输了 $3$ 字节。 - 第 $15$ 毫秒：用户 $2$ 传输了 $4$ 字节。 - 第 $16$ 毫秒：用户 $2$ 传输了 $5$ 字节。 - 第 $17$ 毫秒：用户 $2$ 传输了 $6$ 字节。 - 第 $18$ 毫秒：发生拥塞，没有用户传输数据。 - 第 $19$ 毫秒：用户 $2$ 传输了 $3$ 字节。 - 第 $20$ 毫秒：用户 $2$ 传输了 $4$ 字节。 由 ChatGPT 4.1 翻译