P10439 [JOIST 2024] Escape Route 2 / Escape Route 2

The IOI Kingdom consists of $N$ cities arranged from west to east. The cities are numbered from $1$ to $N$ in order from west to east. In the IOI Kingdom, they use Byou as the unit of time. One day in the IOI Kingdom is divided into $T$ time units. The time $x$ Byous ($0 \leq x < T$) after the start of some day is called time $x$. Therefore, when $1$ Byou passes starting from time $T - 1$ of some day, it becomes time $0$ of the next day. The JOI Organization is one of the secret cults in the IOI Kingdom. Since it is a secret cult, its members must bypass the kingdom’s checkpoints. Therefore, JOI Organization members can only travel between cities using flights operated by JOY Airlines. JOY Airlines offers $M_i$ flights in city $i$ ($1 \leq i \leq N - 1$). Flight $j$ ($1 \leq j \leq M_i$) departs from city $i$ every day at time $A_{i,j}$ and arrives at city $i + 1$ at time $B_{i,j}$ on the same day. Here, $A_{i,j} < B_{i,j}$ holds. These flights provide convenient connections: you may depart immediately after arriving, or stay overnight at the airline’s airport. The JOI Organization has $Q$ members, numbered from $1$ to $Q$. Member $k$ ($1 \leq k \leq Q$) has their operation base in city $L_k$ and their living base in city $R_k$. Therefore, they want to know the shortest time needed to travel from city $L_k$ to city $R_k$, by choosing a departure time from city $L_k$ and taking suitable flights. Given the flights operated by JOY Airlines and the information about the JOI Organization members, write a program to find, for each member $k$, the shortest time to travel from city $L_k$ to city $R_k$.

Read the following data from standard input. - $N$ $T$ - $M_1$ - $A_{1,1}$ $B_{1,1}$ - $A_{1,2}$ $B_{1,2}$ - ... - $A_{1,M_1}$ $B_{1,M_1}$ - $M_2$ - $A_{2,1}$ $B_{2,1}$ - $A_{2,2}$ $B_{2,2}$ - ... - $A_{2,M_2}$ $B_{2,M_2}$ - ... - $M_{N-1}$ - $A_{N-1,1}$ $B_{N-1,1}$ - $A_{N-1,2}$ $B_{N-1,2}$ - ... - $A_{N-1,M_{N-1}}$ $B_{N-1,M_{N-1}}$ - $Q$ - $L_1$ $R_1$ - $L_2$ $R_2$ - ... - $L_Q$ $R_Q$

Output $Q$ lines to standard output. On line $k$ ($1 \leq k \leq Q$), output the shortest time required for member $k$ to travel from city $L_k$ to city $R_k$.

#### Sample Explanation 1 For demonstration, let us call the first day on which member $k$ departs from city $L_k$ Day $1$. Member $1$ can travel from city $1$ to city $3$ in $500$ Byou as follows. 1. Depart from city $1$ at time $100$ on Day $1$, and arrive at city $2$ at time $300$ on Day $1$. 2. Depart from city $2$ at time $300$ on Day $1$, and arrive at city $3$ at time $600$ on Day $1$. Since there is no faster way to travel, output $500$ on line $1$. Member $2$ can travel from city $2$ to city $4$ in $400$ Byou as follows. 1. Depart from city $2$ at time $200$ on Day $1$, and arrive at city $3$ at time $400$ on Day $1$. 2. Depart from city $3$ at time $500$ on Day $1$, and arrive at city $4$ at time $600$ on Day $1$. Since there is no faster way to travel, output $400$ on line $2$. Member $3$ can travel from city $1$ to city $4$ in $10500$ Byou as follows. 1. Depart from city $1$ at time $100$ on Day $1$, and arrive at city $2$ at time $300$ on Day $1$. 2. Depart from city $2$ at time $300$ on Day $1$, and arrive at city $3$ at time $600$ on Day $1$. 3. Depart from city $3$ at time $500$ on Day $2$, and arrive at city $4$ at time $600$ on Day $2$. Since there is no faster way to travel, output $10500$ on line $3$. This sample input satisfies the constraints for Subtasks $2,4,5,6$. #### Sample Explanation 2 This sample input satisfies the constraints for all subtasks. ### Constraints - $2 \leq N \leq 100,000$ - $2 \leq T \leq 10^9$ - $M_i \geq 1$ ($1 \leq i \leq N - 1$) - $M_1 + M_2 + \cdots + M_{N-1} \leq 100,000$ - $0 \leq A_{i,j} < B_{i,j} < T$ ($1 \leq i \leq N - 1, 1 \leq j \leq M_i$) - $1 \leq Q \leq 300,000$ - $1 \leq L_k < R_k \leq N$ ($1 \leq k \leq Q$) - All given values are integers. ### Subtasks 1. (6 points) $N \leq 2,000$, $M_i = 1$ ($1 \leq i \leq N - 1$). 2. (8 points) $N \leq 2,000$, $M_i \leq 5$ ($1 \leq i \leq N - 1$). 3. (17 points) $M_i = 1$ ($1 \leq i \leq N - 1$). 4. (23 points) $M_i \leq 5$ ($1 \leq i \leq N - 1$). 5. (36 points) $N \leq 90,000$, $Q \leq 90,000$, $M_1 + M_2 + \cdots + M_{N-1} \leq 90,000$. 6. (10 points) No additional constraints. Translated by ChatGPT 5