東京大学プログラミングコンテスト2013

H - Asteroids2


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

背景

うさぎ王国と友好関係を築いたうなぎ王国は,今度は宇宙に進出することにした.目標はうなぎ宇宙ステーションの建設である.しかしながら,無数の小惑星に邪魔をされ,広大な空間を占有することができない.そこで王様はレーザー砲を使い,邪魔な小惑星を破壊し尽くすことにした.

課題

N \times N の二次元格子上に M 個の小惑星がある.縦方向(x軸に垂直)もしくは横方向(y軸に垂直)にレーザーを打つことで全ての小惑星を破壊したい.発射されたレーザーは一直線に進み,途中の小惑星を全て貫通してダメージを与える.全てのレーザーは同時に発射され,その出力には,x軸に垂直に直線(x=i)に沿って最大で piy軸に垂直に直線(y=j)に沿って最大で qj の非負整数値を設定することが出来る.小惑星 k は,位置 (xk,yk) にあり,合計出力が ak 以上あれば破壊されるが,合計出力が bk より大きくなると爆発して非常に危険である.どの小惑星も爆発させることなく,全ての小惑星を破壊できるか判定せよ.

配点

200

入力

入力は以下の形式で与えられる.

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

制約

入力中の各変数は以下の制約を満たす.

出力

どの小惑星も爆発させることなく,全ての小惑星を破壊することが可能ならば "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

Submit提出する