#P18790. [KOI2026 二轮] 杂技
[KOI2026 二轮] 杂技
[KOI2026 二轮] 杂技(곡예 / Acrobatics)
题目描述
一根平衡木上有一排 个格子,从左到右编号为 。Alice 和 Bob 在上面表演,每人始终站在恰好一个格子上,并且Alice 的位置必须始终严格小于 Bob 的位置;两人不能站在同一个格子上。
平衡木上有 个跳板。第 个跳板位于格子 ,使用后会精确落在格子 。同一格可以有多个跳板。两人均可使用所有跳板,次数不限。
表演由零次或多次行动组成。每次恰好选择一个人,执行下列一种行动:
- 步行:Alice 可以向右走一格,Bob 可以向左走一格。Alice 不能向左步行,Bob 不能向右步行。
- 跳跃:若此人当前站在格子 ,可以使用第 个跳板跳到 。
每次行动后的落点仍必须满足 Alice 严格在 Bob 左边,否则该行动不允许。跳跃只按题目给定的起点与落点判断,不添加其它限制。
有 个独立计划。计划 表示初始 Alice 在 、Bob 在 ,目标 Alice 在 、Bob 在 。判断是否存在合法行动序列达到目标。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 。
接下来一行一个整数 。
接下来 行,每行四个整数 。
输出格式
每个计划输出一行:可行输出 YES,否则输出 NO。
样例 1
6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2
YES
YES
YES
NO
第二个计划中,Bob 使用 的跳板即可。第四个计划从 出发不能行动:两种步行会使两人重合,Alice 的跳跃会落到 Bob 右边,Bob 的跳跃会落到 Alice 左边。
样例 2
10 3
5 10
6 8
7 4
5
5 6 4 10
5 6 3 9
1 10 2 9
6 8 4 9
9 10 1 10
YES
NO
YES
YES
NO
数据范围与子任务
所有输入均为整数。
- ,,;
- ,;
- 每个计划满足 、。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 8 | |
| 2 | 14 | 所有跳板满足 |
| 3 | 13 | |
| 4 | ||
| 5 | 52 | 无附加限制 |
满分 100 分。时限 2 秒,内存 1024 MiB。