No.2574 Defect-free Rectangles
タグ : / 解いたユーザー数 20
作問者 :
aplysiaSheep
/ テスター :
👑
Kyo_s_s
Magentor
rotti_coder
ragna
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もしくは右上の雲マークをクリックしてアカウントを作成してください。