#P18790. [KOI2026 二轮] 杂技

[KOI2026 二轮] 杂技

[KOI2026 二轮] 杂技(곡예 / Acrobatics)

题目描述

一根平衡木上有一排 NN 个格子,从左到右编号为 1,2,…,N1,2,\ldots,N。Alice 和 Bob 在上面表演,每人始终站在恰好一个格子上,并且Alice 的位置必须始终严格小于 Bob 的位置;两人不能站在同一个格子上。

平衡木上有 MM 个跳板。第 ii 个跳板位于格子 xix_i,使用后会精确落在格子 yiy_i。同一格可以有多个跳板。两人均可使用所有跳板,次数不限。

表演由零次或多次行动组成。每次恰好选择一个人,执行下列一种行动:

  • 步行:Alice 可以向右走一格,Bob 可以向左走一格。Alice 不能向左步行,Bob 不能向右步行。
  • 跳跃:若此人当前站在格子 xix_i,可以使用第 ii 个跳板跳到 yiy_i。

每次行动后的落点仍必须满足 Alice 严格在 Bob 左边,否则该行动不允许。跳跃只按题目给定的起点与落点判断,不添加其它限制。

有 QQ 个独立计划。计划 (a,b,c,d)(a,b,c,d) 表示初始 Alice 在 aa、Bob 在 bb,目标 Alice 在 cc、Bob 在 dd。判断是否存在合法行动序列达到目标。

输入格式

第一行两个整数 N,MN,M。

接下来 MM 行,每行两个整数 xi,yix_i,y_i。

接下来一行一个整数 QQ。

接下来 QQ 行,每行四个整数 a,b,c,da,b,c,d。

输出格式

每个计划输出一行:可行输出 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 使用 3→53\to5 的跳板即可。第四个计划从 (3,4)(3,4) 出发不能行动:两种步行会使两人重合,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

数据范围与子任务

所有输入均为整数。

  • 2≤N≤2000002\le N\le200000,0≤M≤2000000\le M\le200000,1≤Q≤5000001\le Q\le500000;
  • 1≤xi,yi≤N1\le x_i,y_i\le N,xi≠yix_i\ne y_i;
  • 每个计划满足 1≤a<b≤N1\le a<b\le N、1≤c<d≤N1\le c<d\le N。
子任务 分值 附加限制
1 8 N,M,Q≤100N,M,Q\le100
2 14 所有跳板满足 xi<yix_i<y_i
3 13 N≤3000N\le3000
4 Q≤10Q\le10
5 52 无附加限制

满分 100 分。时限 2 秒,内存 1024 MiB。