← 返回题目列表

AtCoder · utpc2013_08

H. 小行星2

中文机器翻译题面 查看原题

問題

背景

与兔子王国建立友好关系的鳗鱼王国,这次决定进军宇宙。目标是建造鳗鱼宇宙站。然而,由于无数的小行星阻碍,无法占据广阔的空间。因此国王决定使用激光炮,把阻碍的小行星彻底摧毁。

課題

N \times N 的二维网格上 M 颗小行星。希望通过沿纵向(垂直于x轴)或横向(垂直于y轴)发射激光来摧毁所有小行星。发射的激光会沿直线前进,穿透途中所有小行星造成伤害。所有激光同时发射,其输出沿x轴的直线(x=i)可以沿着设置最大为 pi,y轴的直线(y=j)可以沿着设置最大为 qj 的非负整数值。小行星 k 位于位置 (xk,yk) ,如果总输出达到 ak 以上则会被摧毁,但如果总输出超过 bk 则会爆炸,非常危险。请判断是否可以在不让任何小行星爆炸的情况下,摧毁所有小行星。

配点

200

入力

输入按以下格式给出。

N M
p1 ... pN
q1 ... qN
x1 y1 a1 b1
...
xM yM aM bM

制約

输入中的每个变量都满足以下约束。

  • 1 \leq N \leq 1000 (=103)
  • 1 \leq M \leq 100000 (=105)
  • 1 \leq pi, qi \leq 1000000 (=106)
  • 1 \leq xi, yi \leq N
  • (xi, yi) \neq (xj, yj) (i \neq j)
  • 1 \leq ak \leq bk \leq 2000000 (=2 \times 106)

出力

如果可以在不让任何小行星爆炸的情况下摧毁所有小行星,则输出 "yes",如果不可能,则输出 "no" 一行。

入力例1

2 3
1 2
3 4
2 1 3 5
1 2 3 4
2 2 6 6

输入示例 1 的输出示例 路径

yes

如下图所示,只要设置激光输出,就可以安全地摧毁所有小行星。

図 1

入力例2

2 3
1 2
3 4
2 1 1 1
1 2 2 3
2 2 5 7

输入示例 2 的输出示例

no