集合 / Set
K. 集合 / Set
时间限制： 1.0 秒 空间限制： 128 MiB
题目描述
滑姬酱有两个大小分别为 n, m 的集合 A, B，它们的元素都是 [0, L] 中的整数，且 0, L 均包含在这两个集合中。现在她想找到一个 最小的集合 C，满足：
- 0, L ∈ C。
- 将 A ∩ C 中的元素从小到大排序后，相邻两项之差均不超过 a。
- 将 B ∩ C 中的元素从小到大排序后，相邻两项之差均不超过 b。 但是滑姬酱太笨笨了所以根本算不出来 QAQ，请救救可怜的滑姬酱喵。为了不给 您造成额外的麻烦，您只需要告诉滑姬酱 C 的大小就可以啦 (> v <) 。特别地，如果满 足条件的 C 不存在，请输出 -1 喵。
输入格式
从标准输入读入数据。 第一行输入五个正整数 n, m, L, a, b(2 ≤ n, m ≤ 106, 1 ≤ a, b ≤ L ≤ 10^18)。 第二行从小到大输入 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
样例 1 输出
9
样例 2 输入
3 4 10 6 4
0 6 10
0 2 7 10
样例 2 输出
-1
样例 3 输入
500 500 10000 143 567
0 21 48 85 137 147 168 192 206 220 223 226 265 293 295 299 302 345 356 362 418 425 430 442 452 459 491 498 532 576 592 596 603 664 679 693 696 765 782 849 853 910 983 992 1018 1020 1026 1044 1079 1102 1109 1112 1120 1125 1129 1132 1142 1144 1147 1162 1163 1195 1241 1258 1268 1299 1309 1327 1367 1370 1386 1428 1446 1474 1500 1521 1538 1553 1619 1658 1687 1735 1785 1812 1831 1854 1911 1920 1959 1978 1996 2000 2025 2060 2075 2077 2079 2098 2106 2160 2183 2193 2194 2211 2233 2259 2274 2282 2287 2338 2345 2359 2370 2395 2398 2403 2421 2450 2463 2488 2492 2503 2515 2531 2559 2595 2625 2649 2651 2689 2702 2707 2718 2733 2745 2747 2759 2774 2790 2799 2843 2845 2852 2875 2893 2909 2923 2928 2942 2963 2973 3016 3027 3052 3126 3130 3142 3147 3204 3219 3222 3231 3242 3248 3253 3255 3257 3273 3312 3349 3372 3406 3438 3442 3457 3482 3486 3525 3549 3585 3602 3668 3707 3740 3819 3857 3987 4012 4018 4036 4049 4085 4094 4100 4103 4110 4117 4142 4163 4172 4227 4253 4282 4297 4327 4333 4353 4371 4382 4489 4525 4546 4576 4595 4604 4667 4691 4707 4743 4789 4796 4811 4813 4837 4840 4845 4869 4901 4908 4962 5009 5015 5034 5050 5058 5108 5140 5158 5159 5181 5233 5249 5264 5324 5348 5359 5371 5378 5404 5423 5495 5522 5609 5616 5640 5673 5709 5713 5717 5722 5723 5754 5755 5763 5771 5816 5848 5864 5882 5918 5922 5934 5945 5955 5968 5992 6000 6009 6046 6063 6079 6140 6150 6159 6174 6186 6189 6210 6228 6235 6242 6244 6268 6284 6291 6298 6321 6323 6358 6386 6401 6410 6419 6444 6471 6493 6522 6524 6526 6528 6547 6586 6665 6677 6707 6738 6742 6858 6866 6878 6882 6886 6900 6914 6917 6973 7009 7022 7033 7047 7060 7062 7101 7145 7148 7202 7227 7278 7286 7287 7298 7362 7408 7415 7439 7441 7445 7455 7480 7481 7482 7489 7499 7509 7521 7528 7542 7559 7628 7629 7643 7647 7651 7657 7680 7697 7702 7703 7723 7732 7735 7736 7766 7767 7777 7792 7820 7823 7843 7858 7870 7883 7910 7915 7917 7947 7964 7970 7989 7996 7997 8029 8060 8066 8082 8133 8221 8223 8234 8241 8245 8258 8261 8277 8324 8335 8375 8389 8395 8416 8421 8431 8502 8521 8525 8550 8566 8567 8594 8597 8602 8606 8613 8626 8629 8635 8636 8656 8662 8663 8666 8695 8703 8714 8715 8723 8745 8757 8779 8798 8800 8808 8850 8853 8858 8874 8889 8898 8911 8941 8969 9010 9014 9016 9019 9072 9126 9138 9140 9155 9156 9171 9186 9195 9232 9246 9294 9296 9332 9365 9371 9397 9470 9475 9498 9509 9512 9528 9549 9598 9601 9624 9625 9664 9712 9721 9732 9735 9756 9767 9792 9810 9816 9847 9851 9881 9895 9968 9974 10000
0 45 55 56 63 130 133 186 192 251 262 268 294 352 418 425 442 459 461 514 518 528 601 603 604 613 616 645 668 672 679 705 775 801 848 849 896 906 911 938 942 950 1018 1028 1033 1047 1091 1095 1115 1125 1129 1183 1210 1212 1222 1288 1331 1343 1395 1411 1429 1443 1446 1469 1484 1491 1554 1571 1588 1606 1644 1648 1656 1659 1670 1692 1705 1715 1763 1774 1796 1810 1834 1911 1928 1941 1949 1959 1976 2000 2034 2035 2060 2072 2077 2078 2082 2127 2145 2193 2203 2215 2220 2229 2232 2233 2247 2263 2287 2294 2316 2353 2380 2395 2425 2488 2504 2505 2522 2529 2590 2595 2610 2635 2636 2649 2655 2695 2707 2713 2727 2731 2744 2762 2774 2790 2802 2821 2845 2848 2917 2927 2935 2942 2953 2982 2988 3002 3006 3012 3017 3025 3117 3135 3184 3195 3222 3240 3246 3248 3253 3257 3276 3302 3303 3316 3337 3357 3366 3372 3373 3418 3457 3466 3479 3499 3525 3546 3547 3549 3559 3603 3612 3637 3653 3747 3832 3841 3868 3904 3905 3921 3924 3988 3990 4040 4041 4051 4054 4057 4083 4135 4154 4172 4216 4242 4251 4287 4304 4330 4333 4355 4378 4380 4404 4408 4478 4506 4515 4517 4521 4544 4546 4548 4578 4602 4763 4768 4796 4808 4814 4845 4906 4922 4985 5019 5026 5034 5050 5061 5091 5127 5134 5162 5180 5182 5183 5223 5257 5259 5357 5376 5378 5419 5442 5462 5500 5512 5520 5521 5525 5534 5554 5564 5584 5602 5617 5634 5642 5651 5656 5673 5682 5727 5745 5754 5759 5763 5771 5791 5798 5804 5816 5824 5841 5846 5849 5854 5859 5860 5862 5873 5887 5888 5894 5898 5915 5922 5936 5938 5968 5991 6024 6032 6055 6140 6172 6189 6191 6201 6220 6284 6290 6298 6312 6321 6341 6358 6368 6379 6436 6466 6477 6500 6505 6560 6600 6632 6663 6665 6674 6727 6735 6750 6759 6819 6838 6850 6867 6878 6900 6909 6925 6943 7037 7047 7075 7107 7113 7155 7208 7212 7245 7252 7286 7287 7322 7324 7367 7374 7411 7415 7455 7471 7498 7499 7509 7510 7521 7522 7528 7542 7553 7629 7647 7656 7673 7680 7697 7717 7723 7752 7759 7761 7769 7810 7820 7829 7837 7843 7850 7860 7862 7897 7905 7929 7939 7953 7956 8036 8059 8081 8101 8124 8133 8162 8187 8197 8261 8263 8288 8298 8303 8307 8317 8320 8340 8389 8394 8395 8405 8424 8476 8500 8513 8531 8597 8635 8639 8666 8680 8696 8735 8769 8776 8780 8810 8812 8816 8822 8824 8826 8834 8871 8895 8909 8910 8948 8977 9016 9019 9071 9101 9104 9106 9140 9150 9171 9195 9203 9207 9253 9274 9299 9329 9336 9339 9360 9365 9371 9397 9437 9472 9520 9549 9559 9586 9601 9646 9660 9662 9663 9674 9687 9700 9712 9733 9767 9783 9801 9803 9816 9822 9858 9888 9921 9933 9986 9987 10000
样例 3 输出
85
样例 1 解释
一个最小的 C 为 {0, 6, 8, 11, 12, 18, 23, 24, 30}, 故答案为 9。
样例 3
见题目目录下的 3.in 与 3.ans。
评论