QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
[0]

# 1907. 博弈

Statistics

这是一道大原题。

给定 n 个矩形,第 i 个大小为 wi×hi。现在有一个博弈,每次玩家可以选择一个矩形,以及一个可以切的方向,均匀切成 n>1 份,要求切完后长宽仍是整数。对于第 i 个矩形,还会有参数 ai,bi{0,1}。若 ai=1,则第 i 个矩形与它切出来的所有小矩形双方都可以在 w 这一维横着切,否则只有左方能横着切。若 bi=1,则第 i 个矩形与它切出来的所有小矩形双方都可以在 h 这一维竖着切,否则只有右方能竖着切。

现在给定 q 个询问,第 i 个询问为若仅留下第 lr 个矩形,左方先手能否获胜。

输入格式

输入的第一行包含两个整数 n,q

接下来 n 行,每行四个整数 ai,bi,wi,hi,描述每个矩形。

接下来 q 行,每行两个整数 li,ri

输出格式

输出一行,对于每个询问,如果可以获胜,输出 Y,否则输出 N

样例数据

样例 1 输入

6 8
1 0 3 5
0 1 5 10
1 1 6 4
1 1 8 12
0 1 4 6
1 0 8 10
1 2
1 4
1 5
2 4
2 5
3 3
3 6
4 4

样例 1 输出

NNNNNYYY

样例 2

见下发文件。

子任务

对于所有数据,1n1051q1061hi,wi1051lirin

  • Subtask 1(10 分):n,q10
  • Subtask 2(20 分):n2000
  • Subtask 3(15 分):ai=bi=1
  • Subtask 4(5 分):ai=1
  • Subtask 5(5 分):bi=1
  • Subtask 6(45 分):没有额外的限制。