Problem:


Score : 2000 points

Problem Statement

You are given an H \times W grid.
The square at the top-left corner will be represented by (0, 0), and the square at the bottom-right corner will be represented by (H-1, W-1).

Of those squares, N squares (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) are painted black, and the other squares are painted white.

Let the shortest distance between white squares A and B be the minimum number of moves required to reach B from A visiting only white squares, where one can travel to an adjacent square sharing a side (up, down, left or right) in one move.

Since there are H × W - N white squares in total, there are _{(H×W-N)}C_2 ways to choose two of the white squares.

For each of these _{(H×W-N)}C_2 ways, find the shortest distance between the chosen squares, then find the sum of all those distances, modulo 1 000 000 007=10^9+7.

Constraints

1 \leq H, W \leq 10^6

1 \leq N \leq 30

0 \leq x_i \leq H-1

0 \leq y_i \leq W-1

If i \neq j, then either x_i \neq x_j or y_i \neq y_j.

There is at least one white square.

For every pair of white squares A and B, it is possible to reach B from A visiting only white squares.

Input

Input is given from Standard Input in the following format:

H W
N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the sum of the shortest distances, modulo 10^9+7.

Sample Input 1

2 3
1
1 1

Sample Output 1

20

We have the following grid (.: a white square, #: a black square).

...
.#.

Let us assign a letter to each white square as follows:

ABC
D#E

Then, we have:

dist(A, B) = 1

dist(A, C) = 2

dist(A, D) = 1

dist(A, E) = 3

dist(B, C) = 1

dist(B, D) = 2

dist(B, E) = 2

dist(C, D) = 3

dist(C, E) = 1

dist(D, E) = 4

where dist(A, B) is the shortest distance between A and B. The sum of these distances is 20.

Sample Input 2

2 3
1
1 2

Sample Output 2

16

Let us assign a letter to each white square as follows:

ABC
DE#

Then, we have:

dist(A, B) = 1

dist(A, C) = 2

dist(A, D) = 1

dist(A, E) = 2

dist(B, C) = 1

dist(B, D) = 2

dist(B, E) = 1

dist(C, D) = 3

dist(C, E) = 2

dist(D, E) = 1

The sum of these distances is 16.

Sample Input 3

3 3
1
1 1

Sample Output 3

64

Sample Input 4

4 4
4
0 1
1 1
2 1
2 2

Sample Output 4

268

Sample Input 5

1000000 1000000
1
0 0

Sample Output 5

333211937



Sample input:
2 3
1
1 1


Sample output:
20

Submission status: Wrong Answer

Solution code:
from collections import deque
mod = 10**9 + 7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = [0]*h
column = [0]*w
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append([x, y])


cnt = 0
top = 0
bottom = h*w - n
area = []
for i in range(h):
    if row[i] == 0:
        cnt += 1
        if i != h-1 and row[i+1] == 0:
            top += w
            bottom -= w
            ans += top*bottom
            ans %= mod
        else:
            area.append([cnt for _ in range(w)])
    else:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([1 for _ in range(w)])
        for x, y in black:
            if x == i:
                area[-1][y] = 0
        cnt = 0

R = len(area)

cnt = 0
left = 0
right = h*w - n
area2 = []
for j in range(w):
    if column[j] == 0:
        cnt += 1
        if j != w-1 and column[j+1] == 0:
            left += h
            right -= h
            ans += left*right
            ans %= mod
        else:
            area2.append([cnt*area[i][j] for i in range(R)])
    else:
        left += w-column[j]
        right -= w-column[j]
        area2.append([area[i][j] for i in range(R)])
        cnt = 0

C = len(area2)
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def bfs(p, q):
    dist = [[10**9 for _ in range(R)] for __ in range(C)]
    visited = [[False for _ in range(R)] for __ in range(C)]
    dist[p][q] = 0
    visited[p][q] = True
    q = deque([(p, q)])
    while q:
        x, y = q.popleft()
        for dx, dy in vec:
            if 0 <= x+dx < C and 0 <= y+dy < R and area2[x+dx][y+dy] != 0:
                if not visited[x+dx][y+dy]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    visited[x+dx][y+dy] = True
                    q.append((x+dx, y+dy))
    return dist


ans2 = 0

for i in range(C):
    for j in range(R):
        d = bfs(i, j)
        for k in range(C):
            for l in range(R):
                ans2 += area2[i][j]*area2[k][l]*d[k][l]
                ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)

Submission status: Wrong Answer

Solution code:
print("bandzebo")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
mod = 10**9+7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = Counter()
column = Counter()
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append((x, y))
row[h] += 1
column[w] += 1


def sqsum(x):
    return x*(x+1)*(2*x+1)//6


pre = -1
top = 0
bottom = h*w - n
area = []
for i in sorted(row.keys()):
    if i == pre+2:
        top += w
        bottom -= w
        area.append([-1, 1])
    elif i > pre+2:
        ans += (i-pre-2)*top*bottom + ((i-pre-2)*(i-pre-1)//2) * \
            w*(bottom-top) - sqsum(i-pre-2)*(w**2)
        ans %= mod
        top += (i-pre-1)*w
        bottom -= (i-pre-1)*w
        area.append([-1, i-pre-1])
    if i != h:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([i])
    pre = i

R = len(area)

pre = -1
left = 0
right = h*w-n
area2 = []
for j in sorted(column.keys()):
    if j == pre+2:
        left += h
        right -= h
        area2.append([area[i][1] if area[i][0] == -1 else 1 for i in range(R)])
    elif j > pre+2:
        ans += (j-pre-2)*left*right + ((j-pre-2)*(j-pre-1)//2) * \
            h*(right-left) - sqsum(j-pre-2)*(h**2)
        ans %= mod
        left += (j-pre-1)*h
        right -= (j-pre-1)*h
        area2.append([(j-pre-1)*area[i][1] if area[i][0]
                      == -1 else (j-pre-1) for i in range(R)])
    if j != w:
        left += h-column[j]
        right -= h-column[j]
        tmp = []
        for i in range(R):
            if area[i][0] == -1:
                tmp.append(area[i][1])
            else:
                if (area[i][0], j) in black:
                    tmp.append(0)
                else:
                    tmp.append(1)
        area2.append(tmp)
    pre = j


C = len(area2)
area2 = [[area2[j][i] % mod for j in range(C)] for i in range(R)]

INF = 10**9+7
d = [[INF]*(R*C) for _ in range(R*C)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(R*C):
    x = i//C
    y = i % C
    if area2[x][y] == 0:
        continue
    for dx, dy in vec:
        j = (x+dx)*C + y+dy
        if 0 <= x+dx < R and 0 <= y+dy < C and area2[x+dx][y+dy] != 0:
            d[i][j] = d[j][i] = 1


def warfl(d, card):
    for i in range(card):
        d[i][i] = 0
    for k in range(card):
        for i in range(card):
            for j in range(card):
                if d[i][k] != INF and d[k][j] != INF:
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


ans2 = 0
d = warfl(d, R*C)

for i in range(R*C):
    for j in range(R*C):
        ans2 += area2[i//C][i % C]*area2[j//C][j % C]*d[i][j]
        ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
mod = 10**9 + 7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = Counter()
column = Counter()
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append((x, y))
row[h] += 1
column[w] += 1


def sqsum(x):
    return x*(x+1)*(2*x+1)//6


pre = -1
top = 0
bottom = h*w - n
area = []
for i in sorted(row.keys()):
    if i == pre+2:
        top += w
        bottom -= w
        area.append([-1, 1])
    elif i > pre+2:
        # for x in range(pre+1, i-1):
        #     top += w
        #     bottom -= w
        #     ans += top*bottom
        #     ans %= mod
        ans += (i-pre-2)*top*bottom + ((i-pre-2)*(i-pre-1)//2) *w*(bottom-top) - sqsum(i-pre-2)*(w**2)
        ans %= mod
        top += (i-pre-1)*w
        bottom -= (i-pre-1)*w
        area.append([-1, i-pre-1])
    if i != h:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([i])
    pre = i

R = len(area)

pre = -1
left = 0
right = h*w-n
area2 = []
for j in sorted(column.keys()):
    if j == pre+2:
        left += h
        right -= h
        area2.append([area[i][1] if area[i][0] == -1 else 1 for i in range(R)])
    elif j > pre+2:
        ans += (j-pre-2)*left*right + ((j-pre-2)*(j-pre-1)//2) *h*(right-left) - sqsum(j-pre-2)*(h**2)
        ans %= mod
        left += (j-pre-1)*h
        right -= (j-pre-1)*h
        area2.append([(j-pre-1)*area[i][1] if area[i][0]
                      == -1 else (j-pre-1) for i in range(R)])
    if j != w:
        left += h-column[j]
        right -= h-column[j]
        tmp = []
        for i in range(R):
            if area[i][0] == -1:
                tmp.append(area[i][1])
            else:
                if (area[i][0], j) in black:
                    tmp.append(0)
                else:
                    tmp.append(1)
        area2.append(tmp)
    pre = j


C = len(area2)
area2 = [[area2[j][i] for j in range(C)] for i in range(R)]

vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def bfs(p, q):
    dist = [[10**5 for _ in range(C)] for __ in range(R)]
    visited = [[False for _ in range(C)] for __ in range(R)]
    dist[p][q] = 0
    visited[p][q] = True
    q = deque([(p, q)])
    while q:
        x, y = q.popleft()
        for dx, dy in vec:
            if 0 <= x+dx < R and 0 <= y+dy < C and area2[x+dx][y+dy] != 0:
                if not visited[x+dx][y+dy]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    visited[x+dx][y+dy] = True
                    q.append((x+dx, y+dy))
    return dist


ans2 = 0

for i in range(R):
    for j in range(C):
        if area2[i][j] == 0:
            continue
        d = bfs(i, j)
        for k in range(R):
            for l in range(C):
                if area2[k][l] == 0:
                    continue
                ans2 += area2[i][j]*area2[k][l]*d[k][l]
                ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
mod = 10**9+7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = Counter()
column = Counter()
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append((x, y))
row[h] += 1
column[w] += 1


def sqsum(x):
    return x*(x+1)*(2*x+1)//6


pre = -1
top = 0
bottom = h*w - n
area = []
for i in sorted(row.keys()):
    if i == pre+2:
        top += w
        bottom -= w
        area.append([-1, 1])
    elif i > pre+2:
        # for x in range(pre+1, i-1):
        #     top += w
        #     bottom -= w
        #     ans += top*bottom
        #     ans %= mod
        ans += (i-pre-2)*top*bottom + ((i-pre-2)*(i-pre-1)//2) * \
            w*(bottom-top) - sqsum(i-pre-2)*(w**2)
        ans %= mod
        top += (i-pre-1)*w
        bottom -= (i-pre-1)*w
        area.append([-1, i-pre-1])
    if i != h:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([i])
    pre = i

R = len(area)

pre = -1
left = 0
right = h*w-n
area2 = []
for j in sorted(column.keys()):
    if j == pre+2:
        left += h
        right -= h
        area2.append([area[i][1] if area[i][0] == -1 else 1 for i in range(R)])
    elif j > pre+2:
        ans += (j-pre-2)*left*right + ((j-pre-2)*(j-pre-1)//2) * \
            h*(right-left) - sqsum(j-pre-2)*(h**2)
        ans %= mod
        left += (j-pre-1)*h
        right -= (j-pre-1)*h
        area2.append([(j-pre-1)*area[i][1] if area[i][0]
                      == -1 else (j-pre-1) for i in range(R)])
    if j != w:
        left += h-column[j]
        right -= h-column[j]
        tmp = []
        for i in range(R):
            if area[i][0] == -1:
                tmp.append(area[i][1])
            else:
                if (area[i][0], j) in black:
                    tmp.append(0)
                else:
                    tmp.append(1)
        area2.append(tmp)
    pre = j


C = len(area2)
area2 = [[area2[j][i] % mod for j in range(C)] for i in range(R)]

# print(R, C)
# for x in area2:
#     print(*x)
# exit()

INF = 10**9+7
d = [[INF]*(R*C) for _ in range(R*C)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(R*C):
    x = i//C
    y = i % C
    if area2[x][y] == 0:
        continue
    for dx, dy in vec:
        j = (x+dx)*C + y+dy
        if 0 <= x+dx < R and 0 <= y+dy < C and area2[x+dx][y+dy] != 0:
            d[i][j] = d[j][i] = 1


def warfl(d, card):
    for i in range(card):
        d[i][i] = 0
    for k in range(card):
        for i in range(card):
            for j in range(card):
                if d[i][k] != INF and d[k][j] != INF:
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


ans2 = 0
d = warfl(d, R*C)

for i in range(R*C):
    for j in range(R*C):
        ans2 += area2[i//C][i % C]*area2[j//C][j % C]*d[i][j]
        ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)

Submission status: Accepted

Solution code:
from collections import deque, Counter
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9 + 7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = Counter()
column = Counter()
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append((x, y))
row[h] += 1
column[w] += 1


def sqsum(x):
    return x*(x+1)*(2*x+1)//6


pre = -1
top = 0
bottom = h*w - n
area = []
for i in sorted(row.keys()):
    if i == pre+2:
        top += w
        bottom -= w
        area.append([-1, 1])
    elif i > pre+2:
        ans += (i-pre-2)*top*bottom + ((i-pre-2)*(i-pre-1)//2) * \
            w*(bottom-top) - sqsum(i-pre-2)*(w**2)
        ans %= mod
        top += (i-pre-1)*w
        bottom -= (i-pre-1)*w
        area.append([-1, i-pre-1])
    if i != h:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([i])
    pre = i

R = len(area)

pre = -1
left = 0
right = h*w-n
area2 = []
for j in sorted(column.keys()):
    if j == pre+2:
        left += h
        right -= h
        area2.append([area[i][1] if area[i][0] == -1 else 1 for i in range(R)])
    elif j > pre+2:
        ans += (j-pre-2)*left*right + ((j-pre-2)*(j-pre-1)//2) * \
            h*(right-left) - sqsum(j-pre-2)*(h**2)
        ans %= mod
        left += (j-pre-1)*h
        right -= (j-pre-1)*h
        area2.append([(j-pre-1)*area[i][1] if area[i][0]
                      == -1 else (j-pre-1) for i in range(R)])
    if j != w:
        left += h-column[j]
        right -= h-column[j]
        tmp = []
        for i in range(R):
            if area[i][0] == -1:
                tmp.append(area[i][1])
            else:
                if (area[i][0], j) in black:
                    tmp.append(0)
                else:
                    tmp.append(1)
        area2.append(tmp)
    pre = j


C = len(area2)
area2 = [[area2[j][i] for j in range(C)] for i in range(R)]

vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def bfs(p, q):
    dist = [[10**5 for _ in range(C)] for __ in range(R)]
    visited = [[False for _ in range(C)] for __ in range(R)]
    dist[p][q] = 0
    visited[p][q] = True
    q = deque([(p, q)])
    while q:
        x, y = q.popleft()
        for dx, dy in vec:
            if 0 <= x+dx < R and 0 <= y+dy < C and area2[x+dx][y+dy] != 0:
                if not visited[x+dx][y+dy]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    visited[x+dx][y+dy] = True
                    q.append((x+dx, y+dy))
    return dist


ans2 = 0

for x in range(R*C):
    i = x//C
    j = x % C
    if area2[i][j] == 0:
        continue
    d = bfs(i, j)
    for y in range(R*C):
        k = y//C
        l = y % C
        if area2[k][l] == 0:
            continue
        ans2 += area2[i][j]*area2[k][l]*d[k][l]
        ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)