P14191 [ICPC 2024 Hangzhou R] Elevator II

There is a building with $10^9$ floors but only $1$ elevator. Initially, the elevator is on the $f$-th floor. There are $n$ people waiting for the elevator. The $i$-th person is currently on the $l_i$-th floor and wants to take the elevator to the $r_i$-th floor ($l_i < r_i$). Because the elevator is so small, it can carry at most $1$ person at a time. It costs $1$ unit of electric energy to move the elevator $1$ floor upwards. No energy is needed if the elevator moves downwards. That is to say, it costs $\max(y - x, 0)$ units of electric energy to move the elevator from the $x$-th floor to the $y$-th floor. Find the optimal order to take all people to their destinations so that the total electric energy cost is minimized. More formally, let $a_1, a_2, \cdots, a_n$ be a permutation of $n$ where $a_i$ indicates that the $i$-th person to take the elevator is $a_i$. The total electric energy cost can be calculated as $$\sum\limits_{i = 1}^n (\max(l_{a_i} - r_{a_{(i - 1)}}, 0) + r_{a_i} - l_{a_i})$$ where $a_0 = 0, r_0 = f$ for convenience. Recall that a sequence $a_1, a_2, \cdots, a_n$ of length $n$ is a permutation of $n$ if and only if each integer from $1$ to $n$ (both inclusive) appears exactly once in the sequence.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case: The first line contains two integers $n$ and $f$ ($1 \le n \le 10^5$, $1 \le f \le 10^9$) indicating the number of people and the initial position of the elevator. For the following $n$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 10^9$) indicating that the $i$-th person wants to go from the $l_i$-th floor to the $r_i$-th floor by elevator. It's guaranteed that the sum of $n$ of all test cases will not exceed $3 \times 10^5$.

For each test case, first output one line containing one integer indicating the minimum total electric energy, then output another line containing $n$ integers $a_1, a_2, \cdots, a_n$ separated by a space indicating the optimal order to carry all people. Note that these $n$ integers must form a permutation of $n$. If there are multiple optimal orders, you can print any of them.