CF1804G.Flow Control
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Raj has a single physical network line that connects his office to the Internet. This line bandwidth is b bytes per millisecond.
There are n users who would like to use this network line to transmit some data. The i -th of them will use the line from millisecond si to millisecond fi inclusive. His initial data rate will be set to di . That means he will use data rate equal to di for millisecond si , and then it will change according to the procedure described below.
The flow control will happen as follows. Suppose there are m users trying to transmit some data via the given network line during millisecond x . Denote as ti the data rate that the i -th of these m users has at the beginning of this millisecond. All ti are non-negative integer values.
- If m=0 , i. e. there are no users trying to transmit data during this millisecond, nothing happens.
- If the sum of all ti is less than or equal to b , each active user successfully completes his transmission (the i -th active user transmits ti bytes). After that, the data rate of each active user grows by 1 , i. e. each ti is increased by 1 .
- If the sum of all ti is greater than b , the congestion occurs and no data transmissions succeed this millisecond at all. If that happens, each ti decreases twice, i. e. each ti is replaced with ⌊2ti⌋ .
Raj knows all the values n , b , si , fi , and di , he wants to calculate the total number of bytes transmitted by all the users in the aggregate.
输入格式
The first line of the input contains two integers n and b ( 1≤n≤2⋅105 , 1≤b≤109 ), the number of users who will use the line and the line bandwidth, respectively.
Each of the following n lines contains three integers si , fi and di ( 1≤si≤fi≤109 , 1≤di≤109 ), denoting that the i -th user will try to transmit data during each millisecond between si and fi inclusive, and the initial data rate of the i -th user.
输出格式
Print one integer — the total number of bytes all users will successfully transmit.
输入输出样例
输入#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
说明/提示
Consider the first example.
- Millisecond 1 : User 1 transmits 2 bytes.
- Millisecond 2 : User 1 transmits 3 bytes.
- Millisecond 3 : Congestion occurs, and no user transmits data.
- Millisecond 4 : User 1 transmits 2 bytes.
- Millisecond 5 : User 1 transmits 3 bytes.
In the second example, at each millisecond from the 7 -th to the 11 -th inclusive, congestion occurs, and the only user decreases their rate twice. However, they don't decrease the speed enough before disconnecting.
Consider the third example.
- Millisecond 1 : User 1 transmits 1 bytes.
- Millisecond 2 : User 1 transmits 2 bytes.
- Millisecond 3 : User 1 transmits 3 bytes.
- Millisecond 4 : User 1 transmits 4 bytes.
- Millisecond 5 : User 1 transmits 5 bytes.
- Millisecond 6 : User 1 transmits 6 bytes.
- Millisecond 7 : Congestion occurs, and no user transmits data.
- Millisecond 8 : User 1 transmits 3 bytes. User 2 transmits 3 bytes.
- Millisecond 9 : Congestion occurs, and no user transmits data.
- Millisecond 10 : User 1 transmits 2 bytes. User 2 transmits 2 bytes.
- Millisecond 11 : User 1 transmits 3 bytes. User 2 transmits 3 bytes.
- Millisecond 12 : Congestion occurs, and no user transmits data.
- Millisecond 13 : User 2 transmits 2 bytes.
- Millisecond 14 : User 2 transmits 3 bytes.
- Millisecond 15 : User 2 transmits 4 bytes.
- Millisecond 16 : User 2 transmits 5 bytes.
- Millisecond 17 : User 2 transmits 6 bytes.
- Millisecond 18 : Congestion occurs, and no user transmits data.
- Millisecond 19 : User 2 transmits 3 bytes.
- Millisecond 20 : User 2 transmits 4 bytes.