{"problem":{"name":"[EGOI 2021] Railway / 瑞士铁路","description":{"content":"有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。） 你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9314"},"statements":[{"statement_type":"Markdown","content":"有一条连接苏黎世和卢加诺的长度为 $s$ 千米的铁路。铁路穿过了美丽的阿尔卑斯山，造就了旅程中壮观的景色。由于一些山口对铁路来说太高了，在线路上修剪了 $t$ 条隧道。第 $i$ 条隧道在距离苏黎世 $a_i$ 千米处开始，在 $b_i$ 千米处结束。（因此，第 $i$ 条隧道的长度为 $b_i-a_i$。）\n\n你有一份两地之间的列车时刻表。从苏黎世到卢加诺有 $m$ 班列车，第 $j$ 班列车在 $c_j$ 分钟发车；从卢加诺到苏黎世有 $n$ 班列车，第 $k$ 班列车在 $d_k$ 分钟发车。所有运行中的列车，无论其方向和是否在隧道内，速度均恒为 $1$ 千米每分钟。路程中没有车站，列车也不会在信号灯处停车。因此，每班列车恰好花费 $s$ 分钟到达终点站。\n\n与铁路的长度相比，列车的长度可以忽略不计，所以在本题中，**请假设每班列车是一个沿铁路移动的点**。\n\n通常情况下，铁路有两条轨道：两个方向各有一条。唯一的例外是隧道。每个隧道只有一条轨道，可以从任何方向通行。\n\n无论何时，只要两班反向运行的列车在隧道外相遇时，他们总是可以安全地经过对方。这包括列车正好在隧道的端点处相遇。但另一方面，如果两班反向运行的列车在隧道内严格$^\\dagger$相遇，就会发生碰撞。\n\n已知隧道信息和列车时刻表，请判断是否会发生碰撞。\n\n$^\\dagger$严格：原文如此（strictly）。\n\n## Input\n\n第一行四个整数 $s,t,m,n$——铁路长度、隧道个数、从苏黎世和卢加诺发车的列车数量。\n\n第二行 $t$ 个整数 $a_i$——每个隧道的起点。\n\n第三行 $t$ 个整数 $b_i$——每个隧道的终点。\n\n第四行 $m$ 个整数 $c_j$——从苏黎世发车的时间。\n\n第五行 $n$ 个整数 $d_k$——从卢加诺发车的时间。\n\n## Output\n\n一行，一个为 `YES` 或 `NO` 的字符串，代表是否会发生碰撞。\n\n[samples]\n\n## Background\n\nDay 2 Problem B.\n\n题面译自 [EGOI2021 railway](https://stats.egoi.org/media/task_description/2021_railway_en.pdf)。\n\n## Note\n\n**样例 $1$ 解释**\n\n在长度为 $100$ 千米的铁路上，有两条隧道：距离苏黎世 $20\\sim 30$ 千米处和 $50\\sim 60$ 千米处。唯一一班从苏黎世发车的列车避开了所有从卢加诺发车的列车，如下：\n\n- 与第一班车在距离苏黎世 $5$ 千米处相遇。\n- 与第二班车在两个隧道间相遇。\n- 与第三班车在距离卢加诺 $10$ 千米处相遇。\n- 第四班车在该班车到站后很久才发车。\n\n---\n\n**样例 $2$ 解释**\n\n两班列车在唯一的隧道中间相撞。\n\n---\n\n**样例 $3$ 解释**\n\n两班列车在隧道靠近苏黎世的一端相遇。\n\n---\n\n**样例 $4$ 解释**\n\n两班列车在隧道靠近卢加诺的一端相遇。\n\n---\n\n**数据范围**\n\n对于全部数据，$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}$。\n\n在前三个子任务中，保证 $s,c_j,d_k$ 均为偶数。\n\n- 子任务一（$14$ 分）：$t,m,n\\le 100$，$s\\le 5\\times 10^3$。\n- 子任务二（$16$ 分）：$t\\le 5\\times 10^3$，$s\\le 10^6$。\n- 子任务三（$41$ 分）：无特殊限制。\n- 子任务四（$29$ 分）：无特殊限制。另外，$s,c_j,d_k$ 不一定是偶数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9314","tags":["2021","O2优化","EGOI（欧洲/女生）"],"sample_group":[["100 2 1 4\n20 50\n30 60\n120\n30 100 200 250","NO"],["1000 1 1 1\n600\n700\n100\n400","YES"],["1000 1 1 1\n600\n700\n100\n300","NO"],["1000 1 1 1\n600\n700\n100\n500","NO"]],"created_at":"2026-03-03 11:09:25"}}