AT_abc370_d [ABC370D] Cross Explosion

[problemUrl]: https://atcoder.jp/contests/abc370/tasks/abc370_d 縦 $ H $ マス、横 $ W $ マスのグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と表します。 はじめ、全てのマスには壁が $ 1 $ 個ずつ立てられています。 以下で説明されるクエリを $ Q $ 個与えられる順に処理した後に、残っている壁の個数を求めてください。 $ q $ 番目のクエリでは整数 $ R_q,\ C_q $ が与えられます。 あなたは $ (R_q,\ C_q) $ に爆弾を置いて壁を爆破します。その結果、以下の処理が行われます。 - $ (R_q,\ C_q) $ に壁が存在する場合は、その壁を破壊して処理を終了する。 - $ (R_q,\ C_q) $ に壁が存在しない場合は、$ (R_q,\ C_q) $ から上下左右に見て最初に現れる壁を破壊する。厳密に述べると、以下の $ 4 $ 個の処理が同時に行われる。 - $ (i,\ C_q) $ に壁が存在して $ (k,\ C_q) $ $ (i\ \lt\ k\ \lt\ R_q) $ に壁が存在しないような $ i\ \lt\ R_q $ が存在する時、$ (i,\ C_q) $ に存在する壁を破壊する。 - $ (i,\ C_q) $ に壁が存在して $ (k,\ C_q) $ $ (R_q\ \lt\ k\ \lt\ i) $ に壁が存在しないような $ i\ \gt\ R_q $ が存在する時、$ (i,\ C_q) $ に存在する壁を破壊する。 - $ (R_q,\ j) $ に壁が存在して $ (R_q,\ k) $ $ (j\ \lt\ k\ \lt\ C_q) $ に壁が存在しないような $ j\ \lt\ C_q $ が存在する時、$ (R_q,\ j) $ に存在する壁を破壊する。 - $ (R_q,\ j) $ に壁が存在して $ (R_q,\ k) $ $ (C_q\ \lt\ k\ \lt\ j) $ に壁が存在しないような $ j\ \gt\ C_q $ が存在する時、$ (R_q,\ j) $ に存在する壁を破壊する。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ Q $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_Q $ $ C_Q $

クエリを全て処理した後に、残っている壁の個数を出力せよ。

### 制約 - $ 1\ \leq\ H,\ W $ - $ H\ \times\ W\ \leq\ 4\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ R_q\ \leq\ H $ - $ 1\ \leq\ C_q\ \leq\ W $ - 入力される値は全て整数 ### Sample Explanation 1 クエリを処理する手順を説明すると次のようになります。 - $ 1 $ 番目のクエリでは $ (R_1,\ C_1)\ =\ (1,\ 2) $ である。 $ (1,\ 2) $ に壁は存在するので $ (1,\ 2) $ の壁が爆破される。 - $ 2 $ 番目のクエリでは $ (R_2,\ C_2)\ =\ (1,\ 2) $ である。 $ (1,\ 2) $ に壁は存在しないので、$ (1,\ 2) $ から上下左右に見て最初に現れる壁である $ (2,2),(1,1),(1,3) $ が爆破される。 - $ 3 $ 番目のクエリでは $ (R_2,\ C_2)\ =\ (1,\ 3) $ である。 $ (1,\ 3) $ に壁は存在しないので、$ (1,\ 3) $ から上下左右に見て最初に現れる壁である $ (2,3),(1,4) $ が爆破される。 全てのクエリを処理した後に残っている壁は $ (2,\ 1),\ (2,\ 4) $ の $ 2 $ 個です。