← 返回题目列表

Codeforces · 1804/G

G. 流量控制

中文机器翻译题面 查看原题

Raj 有一条物理网络线路将他的办公室连接到互联网。该线路带宽为每毫秒 $$$b$$$ 字节。

有 $$$n$$$ 用户想要使用这条网络线路传输一些数据。其中第 $$$i$$$ 将使用从毫秒 $$$s_i$$$ 到毫秒 $$$f_i$$$ 的行(包括毫秒 $$$f_i$$$)。他的初始数据速率将设置为 $$$d_i$$$。这意味着他将使用等于$$$d_i$$$的数据速率,持续毫秒$$$s_i$$$,然后它将根据下面描述的过程进行更改。

流量控制将发生如下。假设有 $$$m$$$ 用户尝试在毫秒 $$$x$$$ 内通过给定的网络线路传输一些数据。将这些$$$m$$$用户中的第$$$i$$$用户在该毫秒开始时的数据速率表示为$$$t_i$$$。所有 $$$t_i$$$ 都是非负整数值。

1. 如果 $$$m = 0$$$,i。 e.在这一毫秒内没有用户尝试传输数据,什么也没有发生。
2. 如果所有 $$$t_i$$$ 的总和小于或等于 $$$b$$$,则每个活动用户成功完成其传输(第 $$$i$$$ 个活动用户传输 $$$t_i$$$ 字节)。此后,每个活跃用户的数据速率增长 $$$1$$$,即。 e.每个 $$$t_i$$$ 增加 $$$1$$$。
3. 如果所有$$$t_i$$$ 的总和大于$$$b$$$,则发生拥塞,并且在这一毫秒内根本没有数据传输成功。如果发生这种情况,每个 $$$t_i$$$ 都会减少两次,i。 e.每个 $$$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$$$(含)之间的每毫秒内传输数据,以及第 $$$i$$$ 个用户的初始数据速率。

输出

打印一个整数 — 所有用户将成功传输的字节总数。

示例

输入 #1

1 3
1 5 2

输出 #1

10

输入 #2

1 10
7 11 1000

输出 #2

0

输入 #3

2 6
1 12 1
8 20 3

输出 #3

64

输入#4

3 10
1 100 1
30 60 20
40 80 6

输出#4

534

注意

考虑第一个例子。

- 毫秒 $$$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$$$ 字节。