P3842 [TJOI2007] Line Segments

On an $n \times n$ grid, there is a line segment in each row. In row $i$, the segment’s left endpoint is $(i, L_i)$ and its right endpoint is $(i, R_i)$. You start from $(1, 1)$, must traverse all the segments along the way, and finally reach $(n, n)$, with the total distance traveled as short as possible. More specifically, at any time you may only move one step down (row index increases by $1$), one step left (column index decreases by $1$), or one step right (column index increases by $1$). Since you cannot move up, when moving down from any row to the next, you must ensure you have already completely traversed the segment in the current row.

The first line contains an integer $n$. Each of the next $n$ lines contains two integers. In the $i$-th of these lines (the overall $(i+1)$-th line), the integers denote $L_i$ and $R_i$.

Output a single integer: the length of the shortest route.

One chosen route is: ``` (1, 1) (1, 6) (2, 6) (2, 3) (3, 3) (3, 1) (4, 1) (4, 2) (5, 2) (5, 6) (6, 6) (6, 4) (6, 6) ``` It is not hard to compute that the total length is $24$. Constraints: For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$, $1 \le L_i \le R_i \le n$. Translated by ChatGPT 5