AdditionalFile7005.zip

#7005. 「THUPC 2026 初赛」集合

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

滑姬酱有两个大小分别为 $n, m$ 的集合 $A, B$ ，它们的元素都是 $[0, L]$ 中的整数，且 $0, L$ 均包含在这两个集合中。现在她想找到一个最小的集合 $C$ ，满足：

• $0, L \in C$。
• 将 $A \cap C$ 中的元素从小到大排序后，相邻两项之差均不超过 $a$。
• 将 $B \cap C$ 中的元素从小到大排序后，相邻两项之差均不超过 $b$。

但是滑姬酱太笨笨了所以根本算不出来 QAQ，请救救可怜的滑姬酱喵。为了不给您造成额外的麻烦，您只需要告诉滑姬酱 $C$ 的大小就可以啦（$>\mathrm{v}<$）。特别地，如果满足条件的 $C$ 不存在，请输出 -1 喵。

输入格式

从标准输入读入数据。

第一行输入五个正整数 $n, m, L, a, b$ $\left(2 \leq n, m \leq 10^{6}, 1 \leq a, b \leq L \leq 10^{18}\right)$。

第二行从小到大输入 $n$ 个不同的自然数，表示集合 $A$ 中的元素，保证其中第一个数为 $0$，最后一个数为 $L$。

第三行从小到大输入 $m$ 个不同的自然数，表示集合 $B$ 中的元素，保证其中第一个数为 $0$，最后一个数为 $L$。

输出格式

输出到标准输出。

输出一个正整数，表示所求集合 $C$ 的大小。特别地，若满足条件的 $C$ 不存在，请输出 -1。

样例 1

输入

10 10 30 8 6
0 2 5 8 11 18 20 21 23 30
0 1 6 12 14 18 21 24 28 30

输出

9

一个最小的 $C$ 为 $\{0,6,8,11,12,18,23,24,30\}$，故答案为 $9$。

样例 2

输入

3 4 10 6 4
0 6 10
0 2 7 10

输出

-1

样例 3

见题目目录下的 3.in 与 3.ans。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。