P9314 [EGOI 2021] Railway / 瑞士铁路

Day 2 Problem B. 题面译自 [EGOI2021 railway](https://stats.egoi.org/media/task_description/2021_railway_en.pdf)。

有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。） 你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在 $c_j$ 分钟发车；从卢加诺到苏黎世有 $n$ 班列车，第 $k$ 班列车在 $d_k$ 分钟发车。所有运行中的列车，无论其方向和是否在隧道内，速度均恒为 $1$ 千米每分钟。路程中没有车站，列车也不会在信号灯处停车。因此，每班列车恰好花费 $s$ 分钟到达终点站。 与铁路的长度相比，列车的长度可以忽略不计，所以在本题中，**请假设每班列车是一个沿铁路移动的点**。 通常情况下，铁路有两条轨道：两个方向各有一条。唯一的例外是隧道。每个隧道只有一条轨道，可以从任何方向通行。 无论何时，只要两班反向运行的列车在隧道外相遇时，他们总是可以安全地经过对方。这包括列车正好在隧道的端点处相遇。但另一方面，如果两班反向运行的列车在隧道内严格$^\dagger$相遇，就会发生碰撞。 已知隧道信息和列车时刻表，请判断是否会发生碰撞。 $^\dagger$严格：原文如此（strictly）。

第一行四个整数 $s,t,m,n$——铁路长度、隧道个数、从苏黎世和卢加诺发车的列车数量。 第二行 $t$ 个整数 $a_i$——每个隧道的起点。 第三行 $t$ 个整数 $b_i$——每个隧道的终点。 第四行 $m$ 个整数 $c_j$——从苏黎世发车的时间。 第五行 $n$ 个整数 $d_k$——从卢加诺发车的时间。

一行，一个为 `YES` 或 `NO` 的字符串，代表是否会发生碰撞。

**样例 $1$ 解释** 在长度为 $100$ 千米的铁路上，有两条隧道：距离苏黎世 $20\sim 30$ 千米处和 $50\sim 60$ 千米处。唯一一班从苏黎世发车的列车避开了所有从卢加诺发车的列车，如下： - 与第一班车在距离苏黎世 $5$ 千米处相遇。 - 与第二班车在两个隧道间相遇。 - 与第三班车在距离卢加诺 $10$ 千米处相遇。 - 第四班车在该班车到站后很久才发车。 --- **样例 $2$ 解释** 两班列车在唯一的隧道中间相撞。 --- **样例 $3$ 解释** 两班列车在隧道靠近苏黎世的一端相遇。 --- **样例 $4$ 解释** 两班列车在隧道靠近卢加诺的一端相遇。 --- **数据范围** 对于全部数据，$1\le s\le 10^9$，$0\le t\le 10^5$，$0\le m,n\le 2\times 10^3$，$0\le a_i < s$，$0 < b_i\le s$，$a_i < b_i$，$b_i < a_{i+1}$，$0\le c_j,d_k\le 10^9$，$c_j < c_{j+1}$，$d_k < d_{k+1}$。 在前三个子任务中，保证 $s,c_j,d_k$ 均为偶数。 - 子任务一（$14$ 分）：$t,m,n\le 100$，$s\le 5\times 10^3$。 - 子任务二（$16$ 分）：$t\le 5\times 10^3$，$s\le 10^6$。 - 子任务三（$41$ 分）：无特殊限制。 - 子任务四（$29$ 分）：无特殊限制。另外，$s,c_j,d_k$ 不一定是偶数。