P5835 [USACO19DEC] Meetings S

There are two barns located at points $0$ and $L$ on a one-dimensional number line ($1 \leq L \leq 10^9$). There are also $N$ cows ($1 \leq N \leq 5 \times 10^4$) at distinct positions on the number line (treat the barns and cows as points). Each cow $i$ starts at position $x_i$ and moves at a speed of 1 unit per second in either the positive or negative direction, represented by an integer $d_i$ equal to $1$ or $-1$. Each cow also has a weight in the range $[1,10^3]$. All cows move at constant speed until one of the following events happens: - If cow $i$ reaches a barn, then cow $i$ stops moving. - When cows $i$ and $j$ occupy the same point, and this point is not a barn, then a meeting happens. At that moment, cow $i$ is given cow $j$'s previous velocity, and vice versa. Note that cows may meet at a non-integer point. Let $T$ be the earliest time such that the total weight of the cows that have stopped moving (because they reached one of the two barns) is at least half of the total weight of all cows. Find the total number of pairwise cow meetings that occur during time $0 \ldots T$ (including time $T$).

The first line contains two space-separated integers $N$ and $L$. The next $N$ lines each contain three space-separated integers $w_i$, $x_i$, and $d_i$. All positions $x_i$ are distinct and satisfy $0 < x_i < L$.

Output one line containing the answer.

### Sample Explanation In this example, the cows move as follows: 1. The first and second cows meet at time 0.5 at position 1.5. At this time, the first cow has velocity -1, and the second cow has velocity 1. 2. The second and third cows meet at time 1 at position 2. At this time, the second cow has velocity −1, and the third cow has velocity 1. 3. The first cow reaches the left barn at time 2. 4. The second cow reaches the left barn at time 3. 5. Since the total weight of the cows that have reached a barn is already at least half of the total weight of all cows, the process stops at this time. If it continued, the third cow would reach the right barn at time 4. Exactly two meetings occur. ### Subtasks Testdata 2 to 4 satisfy $N \leq 10^2$, and for all $i$, $w_i = 1$. Testdata 5 to 7 satisfy $N \leq 10^2$. Problem author: Benjamin Qi. Translated by ChatGPT 5