AT_abc212_f.[ABC212F] Greedy Takahashi

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

题目大意

有 $n$ 座城市和 $m$ 辆公交车，第 $i$ 辆公交车会在 $S_i+0.5$ 时从城市 $A_i$ 出发，在 $T_i+0.5$ 时到达城市 $B_i$ 。

Takahashi 想要在这些城市中旅行。具体的说，当他在 $t$ 时刻时位于城市 $p$ 时，他会按照如下方案移动：

若存在在 $t$ 时刻后从城市 $p$ 出发的公交车，那么选择其中离 $t$ 时刻最近的一辆并乘坐。否则停留在城市 $p$ 不移动。

现在 Takahashi 想要问你 $Q$ 个问题，每个问题的格式如下：

如果 Takahashi 在 $X$ 时刻从城市 $Y$ 出发，那么 $Z$ 时刻时 Takahashi 位于哪辆公交车上或者哪个城市中？

输入格式

第一行三个正整数 $n,m,Q$ 。

接下来 $m$ 行，每行四个正整数 $A_i,B_i,S_i,T_i$ ，描述一辆公交车。

接下来 $Q$ 行，每行三个正整数 $X,Y,Z$ ，描述一个询问。

输出格式

输出共 $Q$ 行，每行一个或两个正整数。

如果是城市，输出城市编号，如果是公交车，输出其起点和终点的城市编号。

Translated by _Ponder_

输入输出样例

输入#1

输出#1

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

输入解题思路，AI测评打分。不知道怎么写?

首页