#10 ここはどこ?

難易度

## ストーリー あなたは左上を原点とする$H \times W$のワールド上で迷子になってしまいました。 「…ここは…どこ?」 今得られる情報は周りの地形、そしてワールド全体の地形図だけです。 『お前のいる場所のヒントをやろう…』 「…!神様!そんなこと言わずに!というかここから出して!帰りたい!」 『お前のx座標は5より小さい…』 「…ねえ話聞いてる?」 『お前のy座標は3より大きい…』 「」 **20:10 追記: クエリ4が「未満」であるべきところを「以上」となっていたのを修正しました。** ## 問題 ワールドの広さ(X方向に$W$, Y方向に$H$)、あなたの居場所のヒントが$N$個与えられます。 あなたが今いる場所として有り得る地点がいくつあるかを求めてください。 ただし、あなたの居場所はワールド内(境界含む)の格子点上($X,Y$座標がともに整数)にあります。 ## 入力 入力は$N+2$行からなり、 - $1$行目にはワールドの広さ $H$ $W$がこの順にスペース区切りで入力されます。 - $2$行目には$N$が与えられます。 - 続く$N$行には下記の形式でクエリが1行あたり1つ与えられます。 ### クエリについて あなたの居場所のヒントは次の形式で与えられます。 $com val$ $com$は$1$以上$4$以下の整数で、次のとおりの意味を表します。 - $1$ - 居場所のX座標が$val$以上であることを意味します。 - $0 \le val \le W$ - $2$ - 居場所のX座標が$val$未満であることを意味します。 - $0 \le val \le W$ - $3$ - 居場所のY座標が$val$以上であることを意味します。 - $0 \le val \le H$ - $4$ - 居場所のY座標が$val$未満であることを意味します。 - $0 \le val \le H$ ## 制約 $1 \le H,W \le 10^9$ $0 \le N \le 10^6$ ### 小課題 以下の制約を満たすテストケースに正解すると満点の$30\%$が与えられます: $1 \le H,W \le 10^3$ $0 \le N \le 10^3$ ## 例 ### 例1 #### 入力 ``` 1 1 0 ``` #### 出力 ``` 4 ``` ワールドの広さは1x1ですが、ありえる点としては次の4つが存在します: - $(0,0)$ - $(0,1)$ - $(1,0)$ - $(1,1)$ ### 例2 #### 入力 ``` 1 1 2 1 1 3 1 ``` #### 出力 ``` 1 ``` ヒントにより居場所は一意に定まりました。 ### 例3 #### 入力 ``` 1000000000 1000000000 2 2 2 4 2 ``` #### 出力 ``` 4 ``` 小課題の制約を満たしませんが、4点しかないことは自明でしょう。