Flow Control
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures, dsu, implementation

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.

Input format:
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.

Output format:
Print one integer — the total number of bytes all users will successfully transmit.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
1 3
1 5 2

Example output:
10

Example input:
1 10
7 11 1000

Example output:
0

Editorial:
The problem is inspired by AIMD algorithm for TCP flow and congestion control.
The key solution idea comes from a real-world networking, every time the congestion happens the difference between the maximum active $$$t_i$$$ and the minimum active $$$t_i$$$ halves. Thus, if all users were to start and to stop at the same time there will be no more than two distinct values of $$$t_i$$$ in just $$$\log C$$$ congestions. Here $$$C$$$ stands for the upper limit on values $$$d_i$$$ and $$$b$$$.
Let's store all the unique values of active $$$t_i$$$ in a hash-map together with a supplementary information. Information we need is the sum of all $$$t_i$$$ right after the last congestion, the number of milliseconds past since the last congestion and so on. Using this information we can compute the time of the next congestion in $$$O(1)$$$.
The processing of one congestion will work in $$$O(d)$$$ time where $$$d$$$ is the current number of distinct values of $$$t_i$$$. We also need to be able to merge two groups when congestion happens, this information will be used to process delete operations. That can be done using DSU with path compression and doesn't add much to the total complexity.
We will call the period between two consecutive congestions an epoch. There are epochs of two types: general and repetitive. A repetitive epoch is an epoch that goes in exactly the same way as the previous epoch. That means no new users appear, no users turn off, the epoch starts with exactly the same values of $$$t_i$$$ as the previous epoch and gets to exactly the same state after the closest congestion happens. All other epochs are called general.
Though the total number of epochs can be large (up to $$$\max(f_i)$$$), there will be no more than $$$n \log{C}$$$ general epochs. Indeed, if no users start or finish data transmission, the process will converge to a repetitive epoch in no more than $$$\log{C}$$$ congestions. Here, $$$C$$$ is the upper bound for $$$b$$$ and values $$$d_i$$$.
Repetitive epochs contain no more than two distinct value of $$$t_i$$$, they can be identified and simulated efficiently. How do we simulate general epochs? There is no need to this efficiently, doing this in $$$O(d)$$$ ($$$d$$$ is the number of distinct $$$t_i$$$) will be efficient enough. One can prove this using amortized analysis with the following potential function. Let $$$d$$$ be the number of distinct values of $$$t_i$$$ and $$$t_0 < t_1 < \ldots < t_{d - 1}$$$ be the sequence of these values. $$$P(epoch) = d + \sum_{i = 0}^{d - 2} \log{(t_{i + 1} - t_i)}$$$.
The total complexity is $$$O(n \log C + n \log n)$$$.