F - クローゼットの配置 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ギガコード君は家を買いました．この家は，左右に H 分割，前後に W 分割された合計 H \times W 個の区画に分かれています．そのうち左から i 番目，前から j 番目のマスを (i, j) で表します．

そのうち N 個の区画には物が置かれています．i 個目の物は，区画 (r_i, c_i) 全体を占めています．また，これらの物が動くことはありません．

ギガコード君は，この家にクローゼットを 1 つ設置することにしました．クローゼットは家の外壁に平行な長方形でなければならず，クローゼットのある区画に物が置かれていてはなりません．しかし，地震が起きた時にクローゼットが動くと良くないので，次の条件を満たす置き方のうち 1 つを選ぶことにしました．

  • クローゼットを向きを変えずにどんな方向に動かそうとしても，物や家の外壁に当たって動かせない．

例えば，次のようなクローゼットの配置ができます．

しかし，条件を満たさないクローゼットの配置はできません．

条件を満たすようなクローゼットの配置はいくつあるか求めてください．

制約

  • 1 \leq H \leq 5 \ 000
  • 1 \leq W \leq 5 \ 000
  • 0 \leq N \leq 201 \ 900
  • 1 \leq r_i \leq H
  • 1 \leq c_i \leq W
  • N 個の物はすべて異なる区画に置かれている
  • 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (2 点) H = 1, W = 1
  2. (11 点) H = 1, W \leq 25
  3. (11 点) H \leq 25, W \leq 25
  4. (19 点) N \leq 10
  5. (16 点) H \leq 100, W \leq 100
  6. (17 点) H \leq 350, W \leq 350
  7. (19 点) H \leq 1500, W \leq 1500
  8. (5 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

H W
N
r_1 c_1
r_2 c_2
 : :
r_N c_N

出力

地震が起きても動かないようなクローゼットの配置の数を出力してください．

注意

入力のサイズが大きいので、高速な入出力（C++ の場合 scanf/printf など）を使うことが推奨されています．

入力例 1

3 3
2
1 1
3 2

出力例 1

4

この入出力例では，クローゼットを配置する方法は下図のように 4 個ありますので，「4」と出力してください．

入力例 2

1 10
3
1 1
1 5
1 8

出力例 2

3

この入力例は H = 1 なので小課題 2 の制約を満たします．
クローゼットを配置する方法は下図のように 3 個あります．

入力例 3

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

出力例 3

11

クローゼットを配置する方法は 11 個あります．自分でも数えてみましょう！

入力例 4

4802 5000
10
254 3330
1713 3331
1712 989
256 988
4192 3521
3602 4991
255 987
3603 3520
256 987
4191 4992

出力例 4

32

この入力例は N = 10 なので小課題 4 の制約を満たします．
小課題 4 には，H, W が大きい場合もあることに注意してください．