CF1804G Flow Control

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.

N/A

N/A

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.