Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. At first, all cells were painted white.

Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.

Compute the following:

For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

Constraints

3 \leq H \leq 10^9

3 \leq W \leq 10^9

0 \leq N \leq min(10^5,H×W)

1 \leq a_i \leq H (1 \leq i \leq N)

1 \leq b_i \leq W (1 \leq i \leq N)

(a_i, b_i) \neq (a_j, b_j) (i \neq j)

Input

The input is given from Standard Input in the following format:

H W N
a_1 b_1
:
a_N b_N

Output

Print 10 lines.
The (j+1)-th ( 0 \leq j \leq 9 ) line should contain the number of the subrectangles of size 3×3 of the grid that contains exactly j black cells.

Sample Input 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

Sample Output 1

0
0
0
2
4
0
0
0
0
0

There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.

Sample Input 2

10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9

Sample Output 2

4
26
22
10
2
0
0
0
0
0

Sample Input 3

1000000000 1000000000 0

Sample Output 3

999999996000000004
0
0
0
0
0
0
0
0
0



Sample input:
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4


Sample output:
0
0
0
2
4
0
0
0
0
0

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline

def main():
    h,w,n = map(int,input().split())
    dg = 10**10
    d = defaultdict(int)

    def f(z):
        x,y = divmod(z,dg)
        if 2 <= x <= h-1 and 2 <= y <= w-1:
            return True
        else:
            False

    for i in range(n):
        a,b = map(int,input().split())
        
        if f((a-1)*dg + b-1):
          d[(a-1)*dg + b-1] += 1
        
        if f((a-1)*dg + b):
          d[(a-1)*dg + b] += 1	
        
        if f((a-1)*dg + b+1):
          d[(a-1)*dg + b+1] += 1

        if f((a)*dg + b-1):
          d[(a)*dg + b-1] += 1
        
        if f(a*dg + b):
          d[a*dg + b] += 1
        
        if f((a)*dg + b+1):
          d[(a)*dg + b+1] += 1
        
        if f((a+1)*dg + b+1):
          d[(a+1)*dg + b+1] += 1
        
        if f((a+1)*dg + b):
          d[(a+1)*dg + b] += 1

        if f((a+1)*dg + b-1):
          d[(a+1)*dg + b-1] += 1
        
        
        
        
    res = [0]*10

    for e in d:
        res[d[e]] += 1

    res[0] = (h-2)*(w-2)-sum(res)

    for e in res:
        print(e)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    h,w,n = map(int,input().split())
    dg = 10**10
    d = dict()

    def f(z):
        x,y = divmod(z,dg)
        if 2 <= x <= h-1 and 2 <= y <= w-1:
            return True
        else:
            False

    for i in range(n):
        a,b = map(int,input().split())
        
        if f((a-1)*dg + b-1):
            if (a-1)*dg + b-1 in d:
                d[(a-1)*dg + b-1] += 1
            else:
                d[(a-1)*dg + b-1] = 1
        
        if f((a-1)*dg + b):
            if (a-1)*dg + b in d:
                d[(a-1)*dg + b] += 1
            else:
                d[(a-1)*dg + b] = 1
        
        if f((a-1)*dg + b+1):
            if (a-1)*dg + b+1 in d:
                d[(a-1)*dg + b+1] += 1
            else:
                d[(a-1)*dg + b+1] = 1

        if f((a)*dg + b-1):
            if (a)*dg + b-1 in d:
                d[(a)*dg + b-1] += 1
            else:
                d[(a)*dg + b-1] = 1
        
        if f(a*dg + b):
            if a*dg + b in d:
                d[a*dg + b] += 1
            else:
                d[a*dg + b] = 1
        
        if f((a)*dg + b+1):
            if (a)*dg + b+1 in d:
                d[(a)*dg + b+1] += 1
            else:
                d[(a)*dg + b+1] = 1
        
        if f((a+1)*dg + b+1):
            if (a+1)*dg + b+1 in d:
                d[(a+1)*dg + b+1] += 1
            else:
                d[(a+1)*dg + b+1] = 1
        
        if f((a+1)*dg + b):
            if (a+1)*dg + b in d:
                d[(a+1)*dg + b] += 1
            else:
                d[(a+1)*dg + b] = 1
        
        if f((a+1)*dg + b-1):
            if (a+1)*dg + b-1 in d:
                d[(a+1)*dg + b-1] += 1
            else:
                d[(a+1)*dg + b-1] = 1
        
        
        
        
    res = [0]*10

    for e in d:
        res[d[e]] += 1

    res[0] = (h-2)*(w-2)-sum(res)

    for e in res:
        print(e)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    h,w,n = map(int,input().split())
    dg = 10**10
    d = dict()

    def f(z):
        x,y = z//dg,z%dg
        if 2 <= x <= h-1 and 2 <= y <= w-1:
            return True
        else:
            False

    for i in range(n):
        a,b = map(int,input().split())
        
        if f((a-1)*dg + b-1):
            if (a-1)*dg + b-1 in d:
                d[(a-1)*dg + b-1] += 1
            else:
                d[(a-1)*dg + b-1] = 1
        
        if f((a-1)*dg + b):
            if (a-1)*dg + b in d:
                d[(a-1)*dg + b] += 1
            else:
                d[(a-1)*dg + b] = 1
        
        if f((a-1)*dg + b+1):
            if (a-1)*dg + b+1 in d:
                d[(a-1)*dg + b+1] += 1
            else:
                d[(a-1)*dg + b+1] = 1

        if f((a)*dg + b-1):
            if (a)*dg + b-1 in d:
                d[(a)*dg + b-1] += 1
            else:
                d[(a)*dg + b-1] = 1
        
        if f(a*dg + b):
            if a*dg + b in d:
                d[a*dg + b] += 1
            else:
                d[a*dg + b] = 1
        
        if f((a)*dg + b+1):
            if (a)*dg + b+1 in d:
                d[(a)*dg + b+1] += 1
            else:
                d[(a)*dg + b+1] = 1
        
        if f((a+1)*dg + b+1):
            if (a+1)*dg + b+1 in d:
                d[(a+1)*dg + b+1] += 1
            else:
                d[(a+1)*dg + b+1] = 1
        
        if f((a+1)*dg + b):
            if (a+1)*dg + b in d:
                d[(a+1)*dg + b] += 1
            else:
                d[(a+1)*dg + b] = 1
        
        if f((a+1)*dg + b-1):
            if (a+1)*dg + b-1 in d:
                d[(a+1)*dg + b-1] += 1
            else:
                d[(a+1)*dg + b-1] = 1
        
        
        
        
    res = [0]*10

    for e in d:
        res[d[e]] += 1

    res[0] = (h-2)*(w-2)-sum(res)

    for e in res:
        print(e)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

h,w,n = map(int,input().split())
dg = 10**10
d = dict()

def f(z):
    x,y = z//dg,z%dg
    if 2 <= x <= h-1 and 2 <= y <= w-1:
        return True
    else:
        False

for i in range(n):
    a,b = map(int,input().split())
    
    if f((a-1)*dg + b-1):
        if (a-1)*dg + b-1 in d:
            d[(a-1)*dg + b-1] += 1
        else:
            d[(a-1)*dg + b-1] = 1
    
    if f((a-1)*dg + b):
        if (a-1)*dg + b in d:
            d[(a-1)*dg + b] += 1
        else:
            d[(a-1)*dg + b] = 1
    
    if f((a-1)*dg + b+1):
        if (a-1)*dg + b+1 in d:
            d[(a-1)*dg + b+1] += 1
        else:
            d[(a-1)*dg + b+1] = 1

    if f((a)*dg + b-1):
        if (a)*dg + b-1 in d:
            d[(a)*dg + b-1] += 1
        else:
            d[(a)*dg + b-1] = 1
    
    if f(a*dg + b):
        if a*dg + b in d:
            d[a*dg + b] += 1
        else:
            d[a*dg + b] = 1
    
    if f((a)*dg + b+1):
        if (a)*dg + b+1 in d:
            d[(a)*dg + b+1] += 1
        else:
            d[(a)*dg + b+1] = 1
    
    if f((a+1)*dg + b+1):
        if (a+1)*dg + b+1 in d:
            d[(a+1)*dg + b+1] += 1
        else:
            d[(a+1)*dg + b+1] = 1
    
    if f((a+1)*dg + b):
        if (a+1)*dg + b in d:
            d[(a+1)*dg + b] += 1
        else:
            d[(a+1)*dg + b] = 1
    
    if f((a+1)*dg + b-1):
        if (a+1)*dg + b-1 in d:
            d[(a+1)*dg + b-1] += 1
        else:
            d[(a+1)*dg + b-1] = 1
    
    
    
    
res = [0]*10

for e in d:
    res[d[e]] += 1

res[0] = (h-2)*(w-2)-sum(res)

for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            p.append([x+j-1,y+k-1])
p.sort()
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
        if p[i]==p[i+1]:
            f+=1
        else:
            ans[f]+=1
            f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            if 2<=x+j-1<=h-1 and 2<=y+k-1<=w-1: 
                p.append([x+j-1,y+k-1])
p.sort()
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    #if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
    if p[i]==p[i+1]:
        f+=1
    else:
        ans[f]+=1
        f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            p.append([x+j-1,y+k-1])
p.sort()
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
        if p[i]==p[i+1]:
            f+=1
        else:
            ans[f]+=1
            f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#すぬけくんの塗り絵
h,w,n=map(int,input().split())
dic={}
for  _ in range(n):
    a,b=map(int,input().split())
    for i in range(a-1,a+2):
        for j in range(b-1,b+2):
            if (i,j) in dic.keys():
                dic[(i,j)]+=1
            else:
                dic[(i,j)]=1
              
howmany=[0 for i in range(10)]
for some in dic.keys():
    a,b=some[0],some[1]
    if 2<=a<=h-1 and 2<=b<=w-1:
        howmany[dic[some]]+=1
J=(h-2)*(w-2)-sum(howmany)
print(J)
for i in range(1,10):
    print(howmany[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
B=[[0 for k in range(W-2)] for j in range(H-2)]
li=[-1,0,1]
Nli=[]
for k in range(N):
    a,b=map(int,input().split())
    for n in range(3):
        for m in range(3):
            if 0<=a-2-li[m]<H-2 and 0<=b-2-li[n]<W-2:
                Nli.append((b-2-li[n])*(H-2)+(a-2-li[m]))
import collections
s = collections.Counter(Nli)
v = list(s.values())
print((H-2)*(W-2)-len(set(Nli)))
for k in range(1,10):
    print(v.count(k))

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
B=[[0 for k in range(W-2)] for j in range(H-2)]
li=[-1,0,1]
for k in range(N):
    a,b=map(int,input().split())
    for n in range(3):
        for m in range(3):
            if 0<=a-2-li[m]<H-2 and 0<=b-2-li[n]<W-2:
                B[a-2-li[m]][b-2-li[n]]+=1
for k in range(10):
    c=0
    for j in range(H-2):
        c+=B[j].count(k)
    print(c)

Submission status: Time Limit Exceeded

Solution code:
l = input().split(" ")
w = int(l[0])
h = int(l[1])
n = int(l[2])

array = [[0 for i in range(h)] for j in range(w)]

for i in range(n):
	l = input().split(" ")
	x = int(l[0]) - 1
	y = int(l[1]) - 1
	for i in range(3):
		for j in range(3):
			if x+j-1 >=0 and x+j-1<w and y+i-1 >=0 and y+i-1<h:
				array[x+j-1][y+i-1] += 1

ans = [0 for i in range(10)]

for i in range(h-2):
	for j in range(w-2):
		ans[array[j+1][i+1]] += 1

for a in ans:
	print(a)

Submission status: Time Limit Exceeded

Solution code:
l = input().split(" ")
w = int(l[0])
h = int(l[1])
n = int(l[2])

array = [[0 for i in range(h)] for j in range(w)]

for i in range(n):
	l = input().split(" ")
	x = int(l[0]) - 1
	y = int(l[1]) - 1
	array[x][y] = 1

ans = [0 for i in range(10)]

for i in range(h-2):
	for j in range(w-2):
		a = 0
		for y in range(3):
			for x in range(3):
				a += array[j+x][i+y]

		ans[a] += 1

for a in ans:
	print(a)

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
ans = [0 for i in range(10)]
ab = []
for i in range(N):
    a,b =map(int,input().split())
    a -= 1
    b -=1
    ab.append([a,b])
ab.sort()
start = set()
h1 = [-2,-2,-2,-1,-1,-1,0,0,0]
w1 = [-2,-1,0,-2,-1,0,-2,-1,0]
for a,b in ab:
    for i in range(9):
        if 0<= a+h1[i]<= H-3 and 0<= b+w1[i]<=W-3:
            start.add((a+h1[i],b+w1[i]))
h2 = [2,2,2,1,1,1,0,0,0]
w2 = [2,1,0,2,1,0,2,1,0]
for a,b in start:
    count = 0
    for i in range(9):
        if [a+h2[i],b+w2[i]] in ab:
            count += 1
    if count:
        ans[count] += 1
ans[0] = (H-2)*(W-2) - sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split())

ans = [0]*10

a = []

if n != 0:
    for i in range(n):
        s = input()
        a.append(s)


for i in range(1,h-1):
    for j in range(1,w-1):
        s = 0
        for p in range(3):
            for q in range(3):
                st = str(i+p) + " " + str(j+q)
                if st in a:
                    s += 1
        if s == 0:
            ans[0] += 1
        else:
            ans[s] += 1

for i in range(10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
dx = [-1,-1,-1,0,0,1,1,1,0]
dy = [-1,0,1,-1,1,-1,0,1,0]
H,W,N = map(int,input().split())
s = []
d = {}
for i in range(N):
    a,b = map(int,input().split())
    for j in range(9):
        A = a + dy[j]
        B = b + dx[j]
        f = 0
        if 2 <= A <= H-1:
            if 2 <= B <= W-1:
                f = 1
        if f == 1:
            if (A,B) not in s:
                d[(A,B)] = 0
                s.append((A,B))
            d[(A,B)] += 1
ans = [(H-2)*(W-2)-len(s),0,0,0,0,0,0,0,0,0]
for (x,y) in s:
    ans[d[(x,y)]] += 1
for i in range(10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
dx = [-1,-1,-1,0,0,1,1,1,0]
dy = [-1,0,1,-1,1,-1,0,1,0]
H,W,N = map(int,input().split())
s = []
d = {}
for i in range(N):
    a,b = map(int,input().split())
    for j in range(9):
        A = a + dy[j]
        B = b + dx[j]
        if A <= 1:
            continue
        if A >= H:
            continue
        if B <= 1:
            continue
        if B >= W:
            continue
        if (A,B) not in s:
            d[(A,B)] = 0
            s.append((A,B))
        d[(A,B)] += 1
ans = [(H-2)*(W-2)-len(s),0,0,0,0,0,0,0,0,0]
for (x,y) in s:
    ans[d[(x,y)]] += 1
for i in range(10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
H,W,N = map(int,input().split())
s = []
d = {}
for i in range(N):
    a,b = map(int,input().split())
    f = 1
    if b <= 1:
        f = 0
    if b >= W:
        f = 0
    if a <= 1:
        f = 0
    if a >= H:
        f = 0
    if f == 1:
        if (a,b) not in s:
            d[(a,b)] = 0
            s.append((a,b))
        d[(a,b)] += 1
    for j in range(8):
        A = a + dy[j]
        B = b + dx[j]
        if A <= 1:
            continue
        if A >= H:
            continue
        if B <= 1:
            continue
        if B >= W:
            continue
        if (A,B) not in s:
            d[(A,B)] = 0
            s.append((A,B))
        d[(A,B)] += 1
ans = [(H-2)*(W-2)-len(s),0,0,0,0,0,0,0,0,0]
for (x,y) in s:
    ans[d[(x,y)]] += 1
for i in range(10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import bisect
from operator import itemgetter

h,w,n = map(int, input().split())
# 黒マス
black = []

# 周囲に黒マスがあるマス
search = set()

for i in range(n):
    a,b = map(int, input().split())
    a-=1
    b-=1
    black.append([a,b])
    for x in [-1,0,1]:
        for y in [-1,0,1]:
            if 1<=a+y<h-1 and 1<=b+x<w-1:
                search.add((a+y,b+x))  # タプル。set()内にリストは格納できない。

# 二分探索のためソート
black.sort(key=itemgetter(1))
black.sort(key=itemgetter(0))

ans = [0]*10
# 探索すべき全マスに対して、周囲の黒マスの数を数える。
for a,b in search:
    p = 0
    for y in [-1,0,1]:
        for x in [-1,0,1]:
            try:
                if [a+y,b+x]==black[bisect.bisect_left(black,[a+y,b+x])]:
                    p+=1
            except:
                continue
    ans[p]+=1
ans[0]=(h-2)*(w-2)-sum(ans[1:])

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect

h,w,n = map(int, input().split())

# 黒マス black[y座標] = [x1,x2,...]
black = dict()

# 周囲に黒マスがあるマス
search = set()

for i in range(n):
    a,b = map(int, input().split())
    a-=1
    b-=1
    for x in [-1,0,1]:
        for y in [-1,0,1]:
            if 1<=a+y<h-1 and 1<=b+x<w-1:
                search.add((a+y,b+x))  # タプル。set()内にリストは格納できない。
    try:
        black[a].append(b)
    except:
        black[a]=[b]

# 二分探索のためソート
for b in black:
    black[b].sort()


ans = [0]*10
# 探索すべき全マスに対して、周囲の黒マスの数を数える。
for a,b in search:
    p = 0
    for y in [-1,0,1]:
        for x in [-1,0,1]:
            try:
                c = black[a+y]
                if b+x==c[bisect.bisect_left(c,b+x)]:
                    p+=1
            except:
                continue
    ans[p]+=1
ans[0]=(h-2)*(w-2)-sum(ans[1:])

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#045d
import numpy as np

H,W,N = map(int, input().split())

#array = np.zeros((1+H,1+W)) #メモリエラー起こすので無理。
ans = [0 for _ in range(11)]

painted_points = list() #黒く塗った点のリスト
is_calculated = dict() #key=座標(a,b)、value:keyの座標を抽出した3*3の座標に当てはめて計算したかのset

for i in range(N):
    a,b = map(int, input().split())
    painted_points.append((a,b))
    #array[a][b] = 1
    is_calculated[(a,b)] = set()
    
#print(array)
#print(is_calculated)

#Nでループを回さないとTLEする。Nで回せば、9*N = 10**6 で済む。

for painted_point in painted_points: #N回ループ
    #print(painted_point)
    a = painted_point[0]
    b = painted_point[1]
    
    for i in range(3):
        for j in range(3): #9回ループ
            if a-i >= 1 and a+3-i <= H+1 and b-j >= 1 and b+3-j <= W+1:
                #print(array[a-i:a+3-i,b-j:b+3-j])
                
                #extracted_array = array[a-i:a+3-i,b-j:b+3-j]
                painted_in_extracted_array = 0
                
                for p in range(3):
                    for q in range(3): #9回ループ
                        
                        #if extracted_array[p][q] == 1 and (p+1,q+1) not in is_calculated[(a-i-1+p+1,b-j-1+q+1)]:
                        if (a-i-1+p+1,b-j-1+q+1) in painted_points and (p+1,q+1) not in is_calculated[(a-i-1+p+1,b-j-1+q+1)]:
                            #print(p+1,q+1) #黒塗りされている点の抽出array内の座標
                            #print(a-i-1+p+1,b-j-1+q+1) #黒塗りされている点の座標
                            
                            is_calculated[(a-i-1+p+1,b-j-1+q+1)].add((p+1,q+1))
                            painted_in_extracted_array += 1
                
                ans[painted_in_extracted_array] += 1

ans[0] = 0
print((H-2)*(W-2) - sum(ans))

for i in range(1,10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

H,W,N = map(int,input().split())
D = defaultdict(bool)
B = []

for _ in range(N):
    a,b = map(lambda x: int(x)-1,input().split())
    D[(a,b)] = True
    B.append((a,b))

ans = [0 for _ in range(10)]

for a,b in B:
    for i in range(9):
        ix,iy = divmod(i,3)
        if a-ix<0 or b-iy<0:
            continue
        black_count = 0
        for j in range(9):
            jx,jy = divmod(j,3)
            if H<=a-ix+jx or W<=b-iy+jy:
                break
            if D[(a-ix+jx,b-iy+jy)]:
                if -ix+jx<0 or (-ix+jx==0 and -iy+jy<0):
                    break
                black_count += 1
        else:
            ans[black_count] += 1

ans[0] = (H-2)*(W-2)-sum(ans)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import collections
import sys
input = sys.stdin.readline

H,W,N = map(int,input().split())

ab = []

eff = []

for i in range(N):
    temp = list(map(int,input().split()))
    ab.append(temp)
    for j in range(3):
        for k in range(3):
            if (temp[0]-j >= 1) & (temp[0]-j <= H-2):
                if (temp[1]-k >= 1) & (temp[1]-k <= W-2):
                    eff.append([temp[0]-j,temp[1]-k])

count = [0 for i in range(10)]

while True:
    if eff == []:
        break
    num = eff.count(eff[0])
    count[num] += 1
    eff = [i for i in eff if i != eff[0]]

count[0] = (H-2) * (W-2) - sum(count)

for i in range(10):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    #input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(10)]
    ans[0] = 0
    for a, b in ab:
        temp = np.zeros((5, 5), dtype=np.int8)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        for i in range(tate_0, tate_1):
            for j in range(yoko_0, yoko_1):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
        # print(temp)
        [ans[np.sum(temp[i:i+3, j:j+3])].add((a+i, b+j)) for i in range(tate_0, tate_1-2) for j in range(yoko_0, yoko_1-2)]

    for i in range(9):
        ans[i+1] = len(ans[i+1])

    print((h-2)*(w-2)-sum(ans))
    for i in ans[1:]:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(10)]
    ans[0] = 0
    for a, b in ab:
        temp = np.zeros((5, 5), dtype=np.int8)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        for i in range(tate_0, tate_1):
            for j in range(yoko_0, yoko_1):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
        # print(temp)
        for i in range(tate_0, tate_1-2):
            for j in range(yoko_0, yoko_1-2):
                ans[np.sum(temp[i:i+3, j:j+3])].add((a+i, b+j))

    for i in range(9):
        ans[i+1] = len(ans[i+1])

    print((h-2)*(w-2)-sum(ans))
    for i in ans[1:]:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(10)]
    ans[0] = 0
    for a, b in ab:
        temp = np.full((5, 5), -1, dtype=np.int8)
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
                else:
                    temp[i, j] = 0
        # print(temp)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        new_temp = temp[tate_0:tate_1, yoko_0:yoko_1]
        for i in range(tate_1-tate_0-2):
            for j in range(yoko_1-yoko_0-2):
                ans[np.sum(new_temp[i:i+3, j:j+3])
                    ].add((a+i+tate_0, b+j+yoko_0))

    for i in range(9):
        ans[i+1] = len(ans[i+1])

    print((h-2)*(w-2)-sum(ans))
    for i in ans[1:]:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = np.full((5, 5), -1, dtype=np.int64)
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
                else:
                    temp[i, j] = 0
        # print(temp)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        new_temp = temp[tate_0:tate_1, yoko_0:yoko_1]
        for i in range(tate_1-tate_0-2):
            for j in range(yoko_1-yoko_0-2):
                cnt = np.sum(new_temp[i:i+3, j:j+3])-1
                ans[cnt].add((a+i-2+tate_0, b+j-2+yoko_0))

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    #input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = np.full((5, 5), -1, dtype=np.int64)
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
                else:
                    temp[i, j] = 0
        # print(temp)
        flag_yoko = [0, 5]
        flag_tate = [0, 5]
        if np.all(temp[:, 0] == np.full((1, 5), -1, dtype=np.int64)):
            if np.all(temp[:, 1] == np.full((1, 5), -1, dtype=np.int64)):
                flag_yoko[0] = 2
            else:
                flag_yoko[0] = 1
        if np.all(temp[:, 4] == np.full((1, 5), -1, dtype=np.int64)):
            if np.all(temp[:, 3] == np.full((1, 5), -1, dtype=np.int64)):
                flag_yoko[1] = 3
            else:
                flag_yoko[1] = 4
        if np.all(temp[0, :] == np.full(5, -1, dtype=np.int64)):
            if np.all(temp[1, :] == np.full(5, -1, dtype=np.int64)):
                flag_tate[0] = 2
            else:
                flag_tate[0] = 1
        if np.all(temp[4, :] == np.full(5, -1, dtype=np.int64)):
            if np.all(temp[3, :] == np.full(5, -1, dtype=np.int64)):
                flag_tate[1] = 3
            else:
                flag_tate[1] = 4
        new_temp = temp[flag_tate[0]:flag_tate[1], flag_yoko[0]:flag_yoko[1]]
        # print(new_temp)
        for i in range(flag_tate[1]-flag_tate[0]-2):
            for j in range(flag_yoko[1]-flag_yoko[0]-2):
                cnt = [new_temp[i+k, j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2+flag_tate[0], b+j-2+flag_yoko[0]))

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,input().split())

l = [[0 for i in range(w)] for j in range(h)]
for _ in range(n):
   a,b = map(int,input().split())
   l[a-1][b-1] += 1


#da[i][j]:(0,0)~(i,j)の長方形の和
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p,q,x,y,da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

da = da_generate(h,w,l)
from collections import defaultdict
dic = defaultdict(int)
for i in range(h-2):
   for j in range(w-2):
      dic[da_calc(i, j, i+2, j+2, da)] += 1
   
for i in range(10):
   print(dic[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None]*25
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i*5+j] = 1
                else:
                    temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2, b+j-2))

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {a*(10**9)+b-1 for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None]*25
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0,3-b),min(5,w-b+3)):
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j] = 1
                else:
                    temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {a*(10**9)+b-1 for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = [None for _ in [0]*25]
        for i in range(5):
            for j in range(5):
                if 0 < a+i-2 <= h and 0 < b+j-2 <= w:
                    if (a+i-2)*(10**9)+b+j-3 in ab_d:
                        temp[i*5+j] = 1
                    else:
                        temp[i*5+j] = 0
        for i in range(3):
            for j in range(3):
                cnt = [temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
                if None not in cnt:
                    ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()