AdditionalFile4157.zip

#4157. 「JOISC 2024 Day4」逃跑路线 2

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOISC 2024 Day4 T1 「逃走経路 2 / Escape Route 2」

IOI 国由 $N$ 个城市组成，这些城市自西向东排成一行，并从西开始编号为 $1$ 到 $N$。

IOI 国的一天被分为 $T$ 秒。在一天开始后的 $x\ (0\le x < T)$ 秒后被称为时刻 $x$。因此，当某天的时刻 $T-1$ 过去一秒后，就变成了下一天的时刻 $0$。

秘密结社 JOI 团是 IOI 国中的一个暗中活动的组织。因为它是一个秘密结社，其成员必须绕开国家的检查点。因此 JOI 团的成员必须通过 JOY 航空的航班来进行城际旅行。

JOY 航空有 $M_i$ 架航班从城市 $i\ (1\le i\le N-1)$ 出发。第 $j\ (1\le j\le M_i)$ 架航班每天在时刻 $A_{i,j}$ 从城市 $i$ 起飞，在同一天的时刻 $B_{i,j}$ 到达城市 $i+1$。这里满足 $A_{i,j}<B_{i,j}$。这些航班中转联程也很方便，可以一到达某个城市就立即出发，也可以在机场过夜。

JOI 团有 $Q$ 个成员，编号为 $1$ 到 $Q$。成员 $k\ (1\le k\le Q)$ 将他的活动据点定为城市 $L_k$，生活据点定为 $R_k$。因此，他们想知道从城市 $L_k$ 出发，通过选择合适的航班到达 $R_k$ 的最小所需时间。

给定 JOY 航空的航班和 JOI 团成员的信息，写一个程序求出成员 $k$ 从 $L_k$ 到 $R_k$ 的最小用时。

输入格式

第一行两个整数 $N,T$。

接下来 $N-1$ 块数据，描述 $N-1$ 个城市的航班。对于每块数据，第一行一个整数 $M_i$，接下来 $M_i$ 行，每行两个整数 $A_{i,j},B_{i,j}$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $L_k,R_k$。

输出格式

输出 $Q$ 行，第 $k\ (1\le k\le Q)$ 行输出从城市 $L_k$ 到 $R_k$ 的最小用时。

样例 1

输入

4 10000
1
100 300
2
200 400
300 600
1
500 600
3
1 3
2 4
1 4

输出

500
400
10500

为了方便描述，我们令成员 $k$ 从城市 $L_k$ 出发的日子为第一天。

成员 $1$ 可以从城市 $1$ 花 $500$ 秒到城市 $3$：

1. 在第一天的时刻 $100$ 从城市 $1$ 出发，在在第一天的时刻 $300$ 到城市 $2$​。
2. 在第一天的时刻 $300$ 从城市 $2$ 出发，在在第一天的时刻 $600$ 到城市 $3$。

因为没有更快的方式，所以第一行输出 $500$。

成员 $2$ 可以从城市 $2$ 花 $400$ 秒到城市 $4$：

1. 在第一天的时刻 $200$ 从城市 $2$ 出发，在在第一天的时刻 $400$ 到城市 $3$​。
2. 在第一天的时刻 $500$ 从城市 $3$ 出发，在在第一天的时刻 $600$ 到城市 $4$。

因为没有更快的方式，所以第二行输出 $400$。

成员 $3$ 可以从城市 $1$ 花 $10500$ 秒到城市 $4$：

1. 在第一天的时刻 $100$ 从城市 $1$ 出发，在在第一天的时刻 $300$ 到城市 $2$​。
2. 在第一天的时刻 $300$ 从城市 $2$ 出发，在在第一天的时刻 $600$ 到城市 $3$。
3. 在第二天的时刻 $500$ 从城市 $3$ 出发，在在第二天的时刻 $600$ 到城市 $4$。

因为没有更快的方式，所以第三行输出 $10500$。

这组样例满足子任务 $2,4,5,6$ 的限制。

样例 2

输入

6 10000
1
100 300
1
400 700
1
500 600
1
300 900
1
200 800
1
1 6

输出

30700

这组样例满足所有子任务的限制。

数据范围与提示

• $2\le N\le 10^5$
• $2\le T\le 10^9$
• $M_i\ge 1\ (1\le i\le N-1)$
• $M_1+M_2+\ldots+M_{N-1}\le 10^5$
• $0\le A_{i,j}<B_{i,j}<T\ (1\le i\le N-1,1\le j\le M_i)$
• $1\le Q\le 3\times 10^5$
• $1\le L_k<R_k\le N\ (1\le k\le Q)$

详细子任务附加限制及分值如下表所示。