A15825 | Flow Control
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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 $s_i$ to millisecond $f_i$ inclusive. His initial data rate will be set to $d_i$ . That means he will use data rate equal to $d_i$ for millisecond $s_i$ , 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 $t_i$ the data rate that the $i$ -th of these $m$ users has at the beginning of this millisecond. All $t_i$ are non-negative integer values.
1. If $m = 0$ , i. e. there are no users trying to transmit data during this millisecond, nothing happens.
2. If the sum of all $t_i$ is less than or equal to $b$ , each active user successfully completes his transmission (the $i$ -th active user transmits $t_i$ bytes). After that, the data rate of each active user grows by $1$ , i. e. each $t_i$ is increased by $1$ .
3. If the sum of all $t_i$ is greater than $b$ , the congestion occurs and no data transmissions succeed this millisecond at all. If that happens, each $t_i$ decreases twice, i. e. each $t_i$ is replaced with $\lfloor \frac{t_i}{2} \rfloor$ .
Raj knows all the values $n$ , $b$ , $s_i$ , $f_i$ , and $d_i$ , he wants to calculate the total number of bytes transmitted by all the users in the aggregate.
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 $s_i$ to millisecond $f_i$ inclusive. His initial data rate will be set to $d_i$ . That means he will use data rate equal to $d_i$ for millisecond $s_i$ , 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 $t_i$ the data rate that the $i$ -th of these $m$ users has at the beginning of this millisecond. All $t_i$ are non-negative integer values.
1. If $m = 0$ , i. e. there are no users trying to transmit data during this millisecond, nothing happens.
2. If the sum of all $t_i$ is less than or equal to $b$ , each active user successfully completes his transmission (the $i$ -th active user transmits $t_i$ bytes). After that, the data rate of each active user grows by $1$ , i. e. each $t_i$ is increased by $1$ .
3. If the sum of all $t_i$ is greater than $b$ , the congestion occurs and no data transmissions succeed this millisecond at all. If that happens, each $t_i$ decreases twice, i. e. each $t_i$ is replaced with $\lfloor \frac{t_i}{2} \rfloor$ .
Raj knows all the values $n$ , $b$ , $s_i$ , $f_i$ , and $d_i$ , 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 \leq n \leq 2 \cdot 10^5$ , $1 \leq b \leq 10^9$ ), the number of users who will use the line and the line bandwidth, respectively.
Each of the following $n$ lines contains three integers $s_i$ , $f_i$ and $d_i$ ( $1 \leq s_i \leq f_i \leq 10^9$ , $1 \leq d_i \leq 10^9$ ), denoting that the $i$ -th user will try to transmit data during each millisecond between $s_i$ and $f_i$ inclusive, and the initial data rate of the $i$ -th user.
Each of the following $n$ lines contains three integers $s_i$ , $f_i$ and $d_i$ ( $1 \leq s_i \leq f_i \leq 10^9$ , $1 \leq d_i \leq 10^9$ ), denoting that the $i$ -th user will try to transmit data during each millisecond between $s_i$ and $f_i$ 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.
- 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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted