問題一覧 > 通常問題

No.2574 Defect-free Rectangles

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 20
作問者 : aplysiaSheep / テスター : 👑 AngrySadEight Kyo_s_s Magentor rotti_coder ragna
お気に入りにしたユーザー ProblemId : 10344 / 自分の提出
問題文最終更新日: 2023-12-01 20:20:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
緑以下コンテスト Extra (順位表) の他の問題:

Problem Statement

This problem is an extension of ABC311 E - Defect-free Squares.
There is a grid with $H$ rows and $W$ columns. The cell at the $i$-th row from the top and the $j$-th column from the left is called $(i,j)$.
Each cell of the grid is either holed or not holed. The holed cells are exactly the $N$ cells $(a_1 ,b_1)$,$(a_2 ,b_2)$,$…$,$(a_N ,b_N)$.

When a tuple of positive integers $(i,j,n,m)$ satisfies the following conditions, the rectangular region whose top-left corner is $(i,j)$ and whose bottom-right corner is $(i+n−1,j+m−1)$ is called a defect-free rectangle.

  • $i$ $+$ $n$ $−$ $1≤H$
  • $j$ $+$ $m$ $−$ $1≤W$
  • For every pair of non-negative integers $(k,l)$ satisfying $0≤k≤n$ $−$ $1$$,0≤l≤m$ $−$ $1$, the cell $(i+k,j+l)$ is not holed.

How many defect-free rectangles are there in the grid?

Constraints

  • $1≤H, W≤3000$
  • $0≤N≤\min(H \times W, 10^5)$
  • $1≤a_i≤H$
  • $1≤b_i≤W$
  • $(a_i, b_i)$ are pairwise distinct
  • All input values are integers

Input

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

Output

Output the number of defect-free rectangles.

Sample

Sample 1
Input
2 3 1
2 3
Output
12

There are $12$ defect-free rectangles in total. Listing the top-left and bottom-right coordinates of each, they are:

  • $(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)$

These are the $12$ rectangles.

Sample 2
Input
3 2 6
1 1
1 2
2 1
2 2
3 1
3 2
Output
0

There may be no defect-free rectangles.

Sample 3
Input
1 1 0
Output
1

A defect-free rectangle may coincide with the entire grid.

Sample 3
Input
1876 1305 10
1292 1011
1161 275
1574 337
1361 1102
104 1091
1770 911
1862 836
1519 441
1669 1222
351 507
Output
800375863050

Note that the answer may not fit in a 32-bit integer.

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