← 返回题目列表

AtCoder · abc212_f

I. 贪婪的高桥

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 城市编号 1 通过 N,和 M 在这些城市之间往返的巴士。的 i第总线 (1 \leq i \leq M) 从市区出发 A_i 时间 S_i+0.5 并到达城市 B_i 时间 T_i+0.5.

高桥将在这些之间旅行 N 城市。当他在城市时 p 时间 t,他将执行以下操作。

  1. 如果有从市内出发的巴士 p 不早于时间 t,乘坐公交车中最早发车的公交车前往另一个城市。
  2. 如果没有这样的巴士,什么也不做,留在城市 p.

高桥重复执行上述操作,直到没有巴士可乘坐。保证所有 M 公交车的发车时间不同,因此乘坐的公交车始终是唯一确定的。此外,换乘巴士所需的时间可以忽略不计。

这是您的任务:流程 Q 查询, i-th (1 \leq i \leq Q) 其内容如下。

  • 如果高桥开始他的城市旅行 Y_i 时间 X_i,他当时会在哪个城市或乘坐哪辆巴士 Z_i?

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)
  • A_i \neq B_i\ (1 \leq i \leq M)
  • 1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)
  • S_i \neq S_j\ (i \neq j)
  • 1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)
  • 1 \leq Y_i \leq N\ (1 \leq i \leq Q)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M Q
A_1 B_1 S_1 T_1
A_2 B_2 S_2 T_2
\hspace{1.8cm}\vdots
A_M B_M S_M T_M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\hspace{1.2cm}\vdots
X_Q Y_Q Z_Q

输出

打印 Q 行。的 i- 第行应包含对 i第一个查询如下。

  • 如果 Takashi 当时在某辆公交车上 Z_i,按顺序打印两个代表公交车出发城市和公交车到达城市的整数,它们之间有一个空格。
  • 否则,即如果高桥当时在某个城市 Z_i,打印代表该城市的整数。

样本输入 1

3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2

示例输出 1

2 3
2
3

在第一个查询中,Takahashi 的行程如下。

  1. 从城市开始 1 时间 1.
  2. 乘坐从市区出发的巴士 1 时间 1.5 并到达城市 2 时间 3.5.
  3. 乘坐从市区出发的巴士 2 时间 3.5 并到达城市 3 时间 5.5.
  4. 由于没有巴士从城市出发 3 时间 5.5 或之后,留在城市 3 (永远)。

时间 5,他将乘坐从 City 出发的巴士 2 并到达城市 3。因此,按照输出部分中的指定,我们应该打印 2 和 3 之间有一个空格。


示例输入 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

示例输出 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1