UOJ Logo Universal Online Judge

UOJ

#880. 【JOISC2024】逃生路线 2

附件下载 统计

IOI 王国由从西向东排列的 N 座城市组成,城市按照从西向东的顺序从 1N 编号。

在 IOI 王国,他们使用 Byou 作为时间单位。IOI 王国的一天被分为 T 个时间单位。从某一天开始后的 x 个 Byous(0x<T)被称为时间 x。因此,当从某一天的时间 T1 开始经过 1 个 Byou 时,将成为下一天的时间 0

JOI 组织是 IOI 王国的秘密教派之一。由于它是一个秘密教派,成员必须绕过国家的检查站。因此,JOI 组织成员只能使用 JOY 航空公司运营的航班进行城市间旅行。

JOY 航空公司在城市 i1iN1)提供 Mi 趟航班。第 j 趟航班(1jMi)每天从城市 i 在时间 Ai,j 起飞,于当天的时间 Bi,j 到达城市 i+1。这里,满足 Ai,j<Bi,j

这些航班提供了便捷的转机服务,也可以在抵达后立即起飞或在公司的机场过夜。

JOI 组织有 Q 名成员,编号从 1Q。成员 k1kQ)将他们的运营基地设在城市 Lk,生活基地设在城市 Rk。因此,他们想知道通过选择从城市 Lk 出发的时间和适当的航班进行,从城市 Lk 出发到城市 Rk 的最短时间。

给定 JOY 航空公司运营的航班和 JOI 组织成员的信息,编写一个程序,找到每个成员 k 从城市 Lk 到城市 Rk 的最短时间。

输入格式

从标准输入中读取以下数据。

  • N T
  • M1
  • A1,1 B1,1
  • A1,2 B1,2
  • ...
  • A1,M1 B1,M1
  • M2
  • A2,1 B2,1
  • A2,2 B2,2
  • ...
  • A2,M2 B2,M2
  • ...
  • MN1
  • AN1,1 BN1,1
  • AN1,2 BN1,2
  • ...
  • AN1,MN1 BN1,MN1
  • Q
  • L1 R1
  • L2 R2
  • ...
  • LQ RQ

输出格式

输出 Q 行到标准输出。在第 k 行(1kQ),输出成员 k 从城市 Lk 到城市 Rk 所需的最短时间。

样例解释 1

作为演示,让我们将成员 k 从城市 Lk 出发的第一天称为第 1 天。成员 1 可以按照以下行动在 500 Byou 内从城市 1 前往城市 3

  1. 1 天时刻 100 从城市 1 出发,并在第 1 天时刻 300 到达城市 2
  2. 1 天时刻 300 从城市 2 出发,并在第 1 天时刻 600 到达城市 3

由于没有更快的旅行方式,所以在第 1 行输出 500

成员 2 可以按照以下行动在 400 Byou 内从城市 2 前往城市 4

  1. 1 天时刻 200 从城市 2 出发,并在第 1 天时刻 400 到达城市 3
  2. 1 天时刻 500 从城市 3 出发,并在第 1 天时刻 600 到达城市 4

由于没有更快的旅行方式,所以在第 2 行输出 400

成员 3 可以按照以下行动在 10500 Byou 内从城市 1 前往城市 4

  1. 1 天时刻 100 从城市 1 出发,并在第 1 天时刻 300 到达城市 2
  2. 1 天时刻 300 从城市 2 出发,并在第 1 天时刻 600 到达城市 3
  3. 2 天时刻 500 从城市 3 出发,并在第 2 天时刻 600 到达城市 4

由于没有更快的旅行方式,所以在第 3 行输出 10500

这个样例输入满足子任务 2,4,5,6 的限制条件。

样例解释 2

这个样例输入满足所有子任务的约束条件。

约束条件

  • 2N100,000
  • 2T109
  • Mi11iN1
  • M1+M2++MN1100,000
  • 0Ai,j<Bi,j<T1iN1,1jMi
  • 1Q300,000
  • 1Lk<RkN1kQ
  • 给定值均为整数。

子任务

  1. (6 分) N2,000Mi=11iN1
  2. (8 分) N2,000Mi51iN1
  3. (17 分) Mi=11iN1
  4. (23 分) Mi51iN1
  5. (36 分) N90,000Q90,000M1+M2++MN190,000
  6. (10 分) 无额外约束条件。