問題一覧 > 通常問題

No.2574 Defect-free Rectangles

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : aplysiaSheepaplysiaSheep / テスター : 👑 AngrySadEightAngrySadEight Kyo_s_sKyo_s_s MagentorMagentor rotti_coderrotti_coder ragnaragna
1 ProblemId : 10344 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-01 20:20:03

問題文

この問題はABC311 E - Defect-free Squares を発展させた問題です。
縦 $H$ 行, 横 $W$ 列のグリッドがあります。グリッドの上から $i$ 行目, 左から $j$ 列目のマスを $(i,j)$ と呼びます。
グリッドの各マスは穴の空いたマスとそうでないマスのどちらかです。穴が空いたマスは $(a_1 ,b_1)$,$(a_2 ,b_2)$,$…$,$(a_N ,b_N)$ のちょうど $N$ マスです。

正整数の組 $(i,j,n,m)$ が次の条件を満たすとき、$(i,j)$ を左上隅, $(i+n−1,j+m−1)$ を右下隅とする長方形領域を 穴のない長方形 と呼びます。

  • $i$ $+$ $n$ $−$ $1≤H$
  • $j$ $+$ $m$ $−$ $1≤W$
  • $0≤k≤n$ $−$ $1$$,0≤l≤m$ $−$ $1$ を満たす全ての非負整数の組 $(k,l)$ に対して、$(i+k,j+l)$ は穴が空いていないマスである。

グリッド内に穴のない長方形は何個ありますか？

制約

  • $1≤H, W≤3000$
  • $0≤N≤\min(H \times W, 10^5)$
  • $1≤a_i≤H$
  • $1≤b_i≤W$
  • $(a_i, b_i)$は互いに異なる
  • 入力される値は全て整数

入力

$H\ W\ N$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$        
$a_N\ b_N$

出力

穴のない長方形の個数を出力せよ。

サンプル

サンプル1
入力
2 3 1
2 3
出力
12

穴のない長方形は全部で $12$ 個あります。左上の座標と右下の座標をそれぞれ示すと、

  • $(1,1),(1,1)$
  • $(1,2),(1,2)$
  • $(1,3),(1,3)$
  • $(2,1),(2,1)$
  • $(2,2),(2,2)$
  • $(1,1),(1,2)$
  • $(1,2),(1,3)$
  • $(2,1),(2,2)$
  • $(1,1),(1,3)$
  • $(1,1),(2,1)$
  • $(1,2),(2,2)$
  • $(1,1),(2,2)$

以上の $12$ 個です。

サンプル2
入力
3 2 6
1 1
1 2
2 1
2 2
3 1
3 2
出力
0

穴のない長方形が存在しない場合もあります。

サンプル3
入力
1 1 0
出力
1

穴のない長方形がグリッド全体と一致する場合もあります。

サンプル3
入力
1876 1305 10
1292 1011
1161 275
1574 337
1361 1102
104 1091
1770 911
1862 836
1519 441
1669 1222
351 507
出力
800375863050

答えは32bit整数に収まらない場合があるので注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。