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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H,W,N=map(int,input().split())
p=[list(map(int,input().split())) for i in range(N)]
d={}
r=[0]*10
for x,y in p:
    x-=1
    y-=1
    c=[[0]*6 for i in range(6)]
    xs,xe=max(x-2,0),min(x+3,H)
    ys,ye=max(y-2,0),min(y+3,W)
    for i in range(xe-xs):
        for j in range(ye-ys):
            c[i+1][j+1]=c[i][j+1]+c[i+1][j]-c[i][j]
            if (xs+i,ys+j) in d:
                c[i+1][j+1]+=1
    dr=[0]*10
    for i in range(xe-xs-2):
        for j in range(ye-ys-2):
            dr[c[i+3][j+3]-c[i][j+3]-c[i+3][j]+c[i][j]]+=1
    for i in range(9):
        r[i]+=dr[i-1]-dr[i]
    d[(x,y)]=1
r[0]+=(H-2)*(W-2)
print(*r,sep='\n')

Submission status: Wrong Answer

Solution code:
H,W,N=map(int,input().split())
p=[list(map(int,input().split())) for i in range(N)]
d={}
r=[(H-2)*(W-2)]+[0]*9
import numpy as np
for x,y in p:
    x-=1
    y-=1
    c=np.array([[1 if (i,j) in d else 0 for j in range(max(y-2,0),min(y+3,W))] for i in range(max(x-2,0),min(x+3,H))])
    dr=[0]*10
    for i in range(len(c)-2):
        for j in range(len(c[0])-2):
            dr[np.sum(c[i:i+3,j:j+3])]+=1
    for i in range(9):
        r[i]+=dr[i-1]-dr[i]
    d[(x,y)]=1
print(*r,sep='\n')

Submission status: Wrong Answer

Solution code:
W,H,N=map(int,input().split())
D={}
for i in range(N):
    a,b=map(int,input().split())
    D[(a-1,b-1)]=1
#print(D)
A=[0 for i in range(10)]
X=[-1,0,1,-1,0,1,-1,0,1]
Y=[1,1,1,0,0,0,-1,-1,-1]
d={}

for i in D:
    
    x=[]
    for j in range(9):
        x.append((i[0]+X[j],i[1]+Y[j]))
    cnt=0
    for k in x:
       
        for l in range(9):
            if k[0]+X[l]<0 or W-1<k[0]+X[l] or k[1]+Y[l]<0 or H-1<k[1]+Y[l]:
                cnt=0
                break
            else:
                if (k[0]+X[l],k[1]+Y[l]) in D:
                    cnt+=1
        A[cnt]+=1
        
        if cnt>=1:
            d[(k[0],k[1])]=1
            #print(k[0],k[1],A)
        cnt=0
for i in range(1,9):
    A[i]//=i
A[0]=(H-2)*(W-2)-sum(A[1:])
#print(A)
for i in range(10):
    print(A[i])

Submission status: Wrong Answer

Solution code:
W,H,N=map(int,input().split())
D={}
for i in range(N):
    a,b=map(int,input().split())
    D[(a-1,b-1)]=1
#print(D)
A=[0 for i in range(10)]
X=[-1,0,1,-1,0,1,-1,0,1]
Y=[1,1,1,0,0,0,-1,-1,-1]
d={}

for i in D:
    
    x=[]
    for j in range(9):
        x.append((i[0]+X[j],i[1]+Y[j]))
    cnt=0
    for k in x:
       
        for l in range(9):
            if k[0]+X[l]<0 or W-1<k[0]+X[l] or k[1]+Y[l]<0 or H-1<k[1]+Y[l]:
                cnt=0
                break
            else:
                if (k[0]+X[l],k[1]+Y[l]) in D:
                    cnt+=1
        A[cnt]+=1
        
        if cnt>=1:
            d[(k[0],k[1])]=1
            #print(k[0],k[1],A)
        cnt=0
for i in range(1,9):
    A[i]//=i
A[0]=(H-2)*(W-2)-sum(A[1:])
#print(A)
for i in range(9):
    print(A[i])

Submission status: Wrong Answer

Solution code:
import collections
H,W,N = map(int,input().split())
abList = []
for _ in range(N):
    a,b = map(int, input().split())
    abList.append((a-1,b-1))
memo = []

for a,b in abList:
    for i in range(a-1,a+2):
        if H < i+2 or i < 1:
            continue
        for j in range(b-1, b+2):
            if W < j+2 or j < 1:
                continue
            memo.append((i,j))
x = collections.Counter(memo)
result = [0 for _ in range(9)]
s = 0
for k,v in x.items():
    if int(v) < 9:
        result[int(v)] += 1
    s += int(v)
print((W-2)*(H-2) - len(x))
for x in result:
    print(x)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10000)

H, W, N = (int(i) for i in input().split())
if N == 0:
    reslis = [0] * 10
else:
    L = []
    for k in range(N):
        a, b = (int(i) for i in input().split())
        for i in range(3):
            for j in range(3):
                if 1 <= a - 2 + i <= H - 2 and 1 <= b - 2 + j <= W - 2:
                    L.append((a-2 + i, b-2 + j))
    L.sort()
    temp = None
    cc = 1
    reslis = [0] * 10
    for se in L:
        if temp == se:
            cc += 1
        else:
            if temp == None:
                pass
            else:
                reslis[cc] += 1
                cc = 1
            temp = se
    reslis[cc] += 1

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

for i in reslis:
    print(i)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10000)

H, W, N = (int(i) for i in input().split())
L = []
for k in range(N):
    a, b = (int(i) for i in input().split())
    for i in range(3):
        for j in range(3):
            if 1 <= a - 2 + i <= H - 2 and 1 <= b - 2 + j <= W - 2:
                L.append((a-2 + i, b-2 + j))
L.sort()
temp = None
cc = 1
reslis = [0] * 10
for se in L:
    if temp == se:
        cc += 1
    else:
        if temp == None:
            pass
        else:
            reslis[cc] += 1
            cc = 1
        temp = se
reslis[cc] += 1

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

for i in reslis:
    print(i)

Submission status: Wrong Answer

Solution code:
h,w,n=map(int, input().split())
m=dict()
for _ in range(n):
    a,b=map(int, input().split())
    for i in range(3):
        for j in range(3):
            m[(a+i-1,b+j-1)]=m.get((a+i-1,b+j-1),0)+1
ans=[0]*10
for i,j in m.items():
    c,d=i
    if 1<c<4 and 1<d<5:
        ans[j]+=1
ans[0]=(w-2)*(h-2)-sum(ans)
for i in ans:print(i)

Submission status: Wrong Answer

Solution code:
ai_ = lambda: [int(x)-1 for x in input().split()]
ai = lambda: list(map(int, input().split()))

h,w,n = ai()
bl = [ai_() for _ in range(n)]
from collections import defaultdict
d = defaultdict(int)

from itertools import product

for a,b in bl:
    for da,db in product((-1,0,1), repeat=2):
        print(a+da,b+db)
        if 0 < a+da < h-1 and 0 < b+db < w-1:
            d[(a+da, b+db)] += 1

print((h-2)*(w-2) - len(d))
l = list(d.values())
for i in range(1, 10):
    print(l.count(i))

Submission status: Wrong Answer

Solution code:
import numpy as np

def snuke_coloring(h, w, poses):
    counts = np.zeros(10, np.int64)
    searched = {}

    for pos in poses:
        for y in range(max(1, pos[0] - 2), min(h - 2, pos[0]) + 1):
            for x in range(max(1, pos[1] - 2), min(w - 2, pos[1]) + 1):
                index = (y - 1) * w + (x - 1)
                if index in searched: continue
                searched[index] = True

                count = 0
                for target in poses:
                    if x <= target[1] and target[1] <= x + 2 and \
                       y <= target[0] and target[0] <= y + 2:
                       count += 1
                counts[count] += 1

    nonzero_count = int(np.sum(counts))
    counts[0] = (h - 2) * (w - 2) - nonzero_count
    print(counts)

h, w, n = map(int, input().split())
poses = [tuple(map(int, input().split())) for _ in range(n)]
snuke_coloring(h, w, poses)

Submission status: Wrong Answer

Solution code:
def __main__():
    h, w, n = list(map(int, input().split()))
    grid = []
    for i in range(h):
        row = []
        for j in range(w):
            row.append(0)
        grid.append(row)
    for i in range(n):
        ai, bi = list(map(int, input().split()))
        grid[ai - 1][bi - 1] = 1
    
    result = [0] * 10
    for i in range(h - 2):
        for j in range(w - 2):
            black = 0
            for i2 in range(3):
                for j2 in range(3):
                    if grid[i + i2][j + j2] == 1: black += 1 
            result[black] += 1
            
    for i in range(9):
        print(result[i])

__main__()

Submission status: Wrong Answer

Solution code:
def count(i,j,array):
    count = 0
    for a in range(i-1,i+2):
        for b in range(j-1,j+2):
            if array[a][b] == 1:
                count += 1
    return count

def main():
    h, w, n = [int(k) for k in (input().split())]
    array = []
    for i in range(h):
        array.append([])
        for j in range(w):
            array[i].append(0)
    for i in range(n):
        a, b = [int(k)-1 for k in (input().split())]
        array[a][b] = 1
    
    sum = 0
    for i in range(9):
        for j in range(1,h-1):
            for k in range(1,w-1):
                if count(j,k,array) == i:
                    sum += 1
        print(sum)
        sum = 0 

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
poss = [list(map(int, input().split())) for _ in range(N)]
d = defaultdict(int)
for a, b in poss:
    for i, j in ((i, j) for i in range(a-1, a+2) for j in range(b-1, b+2)):
        s = str(i)+":"+str(j)
        d[s] += 1
def notedge(k):
    i, j = map(int, k.split(":"))
    if 1<i<H and 1<j<W:
        return True
    else:
        return False
d = {k:x for k, x in d.items() if notedge(k)}
anss = [0] * 9
for x in d.values():
    anss[x] += 1
print((H-2)*(W-2) - sum(anss[1:]))
for ans in anss[1:]:
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections
h,w,n=map(int, input().split())
cells = collections.defaultdict(int)
for _ in range(n):
    a,b = map(int, input().split())
    for y in range(-1,2):
        if a+y-1 < 1 or w<a+y+1:
            continue
        for x in range(-1,2):
            if b+x-1 < 1 or h<b+x+1:
                continue
            cells[str(a+y) + '_' + str(b+x)] += 1

counts = [0 for i in range(10)]
for k,v in cells.items():
    counts[v] += 1
counts[0] = (h-2)*(w-2) - sum(counts)
print('\n'.join([str(x) for x in counts]))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

H, W, N = map(int,input().split())
blacks = []
for i in range(N):
    blacks.append(tuple(map(int,input().split())))
square = [[0 for i in range(2,W)] for j in range(2,H)]
D = [(0,0), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1)]

for b in blacks:
    for d in D:
        x = b[0] + d[0]
        y = b[1] + d[1]
        if 2<=x<=H-1 and 2<=y<=W-1: square[x-2][y-2] += 1
        else :continue

square_2d = list(itertools.chain.from_iterable(square))
for i in range(10):
    print(collections.Counter(square_2d)[i])

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int,input().split())              
paints = []                                     
for i in range(N):
    paints.append(tuple(map(int,input().split())))
D = [(0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1)]
black_square = [0 for i in range(10)]

for i in range(2,H):
    for j in range(2,W):
        count = 0
        if (i,j) in paints: count += 1
        for k in range(8):
            if (i + D[k][0], j + D[k][1]) in paints: count += 1
        black_square[count] += 1

for b in black_square:
    print(b)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

H, W, N = getlist()
D = defaultdict(int)
D[0] += (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append((a - j, b - k))

L = sorted(L)
n = len(L)
if n != 0:
	v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		D[c] += 1
		c = 1
	v = L[i]

if n != 0:
	D[c] += 1
for i in range(1, 10):
	D[0] -= D[i]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

H, W, N = getlist()
D = defaultdict(int)
D[0] += (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append([a - j, b - k])

L = sorted(L)
n = len(L)
if n != 0:
	v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		D[c] += 1
		c = 1
	v = L[i]

if n != 0:
	D[c] += 1
for i in range(1, 10):
	D[0] -= D[i]

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

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    H, W, N = map(int, input().split())
    checked = collections.defaultdict(set)
    black = collections.defaultdict(set)
    refs = []
    for _ in range(N):
        a, b = map(int, input().split())
        black[a].add(b)
        refs.append([a, b])

    ans = [0 for _ in range(10)]
    for a, b in refs:
        for da in [-1, 0, 1]:
            for db in [-1, 0, 1]:
                c, d = a+da, b+db
                if d not in checked[c]:
                    checked[c].add(d)
                    if all(1<=c+dc<=H and 1<=d+dd<=W for dc in [-1,0,1] for dd in[-1, 0, 1]):
                        count = 0
                        for dc in [-1, 0, 1]:
                            for dd in [-1, 0, 1]:
                                if d+dd in black[c+dc]:
                                    count += 1
                        ans[count] += 1
    ans[0] = (H-2)*(W-2) - sum(ans[1:]) 
    for i in range(10):
        print(ans[i])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
d = {}
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for i in range(N):
    a, b = map(int, input().split())
    for v in [a - 1, a, a + 1]:
        if v < 2 or v > H - 1:
            continue
        for w in [b - 1, b, b + 1]:
            if w < 2 or w > W - 1:
                continue
            black = 0
            for x in [v - 1, v, v + 1]:
                for y in [w - 1, w, w + 1]:
                    black += d.get((x, y), 0)
            ans[black] -= 1
            ans[black + 1] +=1
            #print(a, b, black, ans)
    d[a, b] = 1
    #print(d)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int,input().split(" "))
ar = [["W" for i in range(b)]for j in range(a)]
br = [0,0,0,0,0,0,0,0,0,0]
for i in range(c):
    l = input().split(" ")
    ar[int(l[0])-1][int(l[1])-1] = "B"
count = 0
for j in range(b-2):
    for i in range(a-2):
        if ar[i][j] =="B":
            count += 1
        if ar[i][j+1] == "B":
            count += 1
        if ar[i][j+2] == "B":
            count += 1
        if ar[i+1][j] == "B":
            count += 1
        if ar[i+1][j+1] == "B":
            count += 1
        if ar[i+1][j+2] == "B":
            count += 1
        if ar[i+2][j] == "B":
            count += 1
        if ar[i+2][j+1] == "B":
            count += 1
        if ar[i+2][j+2] == "B":
            count += 1
        br[count] += 1
        count = 0
for r in br:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def snuke_coloring(h, w, poses):
    counts = np.zeros(10, np.int64)
    searched = {}

    for pos in poses:
        for y in range(max(1, pos[0] - 2), min(h - 2, pos[0]) + 1):
            for x in range(max(1, pos[1] - 2), min(w - 2, pos[1]) + 1):
                index = (y - 1) * w + (x - 1)
                if index in searched: continue
                searched[index] = True

                count = 0
                for target in poses:
                    if x <= target[1] and target[1] <= x + 2 and \
                       y <= target[0] and target[0] <= y + 2:
                       count += 1
                counts[count] += 1

    nonzero_count = int(np.sum(counts))
    counts[0] = (h - 2) * (w - 2) - nonzero_count
    for v in counts: print(v)

h, w, n = map(int, input().split())
poses = [tuple(map(int, input().split())) for _ in range(n)]
snuke_coloring(h, w, poses)

Submission status: Time Limit Exceeded

Solution code:
F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*10;*R,=range(9)
for Y,X in S:
	for A in R:
		P=A,B=X-A%3,Y-A//3
		if(0<A<W-1)*(0<B<H-1)*(P not in T):T.add(P);Z[sum((B+C//3,A+C%3)in S for C in R)]+=1
Z[0]+=(H-2)*(W-2)-sum(Z);print(*Z,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
a=[int(i) for i in input().split()]
b=[]
for i in range(a[2]):
  b.append([int(j) for j in input().split()])
count=[0 for j in range(9)]
suma=[0 for j in range(10)]
han=0
for i in range(len(b)):
  for (j,jj) in enumerate([[-2,-1,0],[-1,0,1],[0,1,2]]):
    for (k,kk) in enumerate([[-2,-1,0],[-1,0,1],[0,1,2]]):
      count[j+3*k]=1
      for n in range(3):
        for m in range(3):
         if 0<b[i][0]+jj[n]<a[0]+1 and 0<b[i][1]+kk[m]<a[1]+1:
          if [b[i][0]+jj[n],b[i][1]+kk[m]] in b:
           if not (jj[n]==0 and kk[m]==0):
            count[j+3*k]+=1
         else:
           han=1
      if han==1:
        han=0
        count[j+3*k]=0
      suma[count[j+3*k]]+=1
      count[j+3*k]=0
su=0
for i in range(1,10):
    suma[i]=int(suma[i]/i)
    su+=suma[i]
suma[0]=(a[0]-2)*(a[1]-2)-su
for i in range(10):
 print(suma[i])

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, raw_input().split())
D = dict()

for i in range(N):
    a, b = map(int, raw_input().split())
    for a_add in [-1, 0, 1]:
        for b_add in [-1, 0, 1]:
            c = a + a_add
            d = b + b_add
            if c-1 in range(1, H-1) and d-1 in range(1, W-1):
                if str([c, d]) in D.keys():
                    D[str([c, d])] += 1
                else:
                    D[str([c, d])] = 1

res_list = [0]*10
for s in D.keys():
    res_list[D[s]] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if 2 > xx or xx > H-1 or 2 > yy or yy > W-1:
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for v in count.values():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if not(2 <= xx <= H-1 and 2 <= yy <= W-1):
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for v in count.values():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if not(2 <= xx <= H-1 and 2 <= yy <= W-1):
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for k, v in count.items():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect_left as bl
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
A.sort()
ans = [0] * 10
for x, y in A:
    for ltx, lty in product(range(max(1, x-2), min(x+1, H-1)), 
                            range(max(1, y-2), min(y+1, W-1))):
        num = sum(bl(A, (ltx+i, lty+3)) - bl(A, (ltx+i, lty)) for i in range(3))
        ans[num] += 1
for i in range(1, len(ans)):
    ans[i] //= i
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
d = defaultdict(int)
for _ in range(N):
    a, b = map(int, input().split())
    for i, j in ((i, j) for i in range(a-1, a+2) for j in range(b-1, b+2)):
        if 1<i<H and 1<j<W:
            s = str(i)+":"+str(j)
            d[s] += 1
anss = [0] * 10
for x in d.values():
    anss[x] += 1
print((H-2)*(W-2) - sum(anss[1:]))
for ans in anss[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
poss = [list(map(int, input().split())) for _ in range(N)]
d = defaultdict(int)
for a, b in poss:
    for i, j in ((i, j) for i in range(a-1, a+2) for j in range(b-1, b+2)):
        if 1<i<H and 1<j<W:
            s = str(i)+":"+str(j)
            d[s] += 1
anss = [0] * 10
for x in d.values():
    anss[x] += 1
print((H-2)*(W-2) - sum(anss[1:]))
for ans in anss[1:]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 

H,W,N = map(int,sys.stdin.readline().split())
painted = []
for i in range(N):
        painted.append(map(int,sys.stdin.readline().split()))
#H,W,N = 4,5,8
#painted = [[1, 1], [1, 4], [1, 5], [2, 3], [3, 1], [3, 2], [3, 4], [4, 4]]
table = [0]*10
def checkfrom(i,j):
        ret = 0 
        for I in range(i,i+3):                                                                                   
                for J in range(j,j+3):
#                       print "I,J is", I,J
                        if [I+1,J+1] in painted:
    
                        #       print "I,J is", I,J
                                ret +=1 
        return ret 
for i in range(H-2):
        for j in range(W-2):
                table[checkfrom(i,j)] += 1
#               print "##"
for i in table:
        print i

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int,raw_input().split())
ab = []
for i in range(n):
    a, b = map(int,raw_input().split())
    ab.append([a,b])
m = [[0 for i in range(w+2)] for j in range(h+2)]
for i in ab:
    for d in [[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]]:
        m[i[0]+d[0]][i[1]+d[1]] += 1
ans = [0 for i in range(10)]
for i in range(2,h):
    for j in range(2,w):
        ans[m[i][j]] += 1
for i in ans:
    print i

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
poss = [list(map(int, input().split())) for _ in range(N)]
d = defaultdict(int)
for a, b in poss:
    for i, j in ((i, j) for i in range(a-1, a+2) for j in range(b-1, b+2)):
        s = str(i)+":"+str(j)
        d[s] += 1
def notedge(k):
    i, j = map(int, k.split(":"))
    if 1<i<H and 1<j<W:
        return True
    else:
        return False
d = {k:x for k, x in d.items() if notedge(k)}
anss = [sum(1 for k, x in d.items() if x==i) for i in range(1, 10)]
print((H-2)*(W-2) - sum(anss))
for ans in anss:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
H,W,N = map(int,input().split())
a = [0] * N
b = [0] * N
xs = [(0,0)] * N
for i in range(N):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    xs[i] = (b[i],a[i])


xs.append( (-2,-2) )
xs.append( (int(1e9),int(1e9)) )
xs.sort()

def search(x,y,xs):
    dxy = [-1,0,1]
    s = 0
    for dx in dxy:
        for dy in dxy:
            nx = x + dx
            ny = y + dy
            p = bisect.bisect_left(xs,(nx,ny))
            if xs[p] == (nx,ny):
                s += 1
    if s == 0:
        print((x,y))
    return s

used = set()
dxy = [-1,0,1]
ans = [0] * 10

for i in range(N):
    for dx in dxy:
        for dy in dxy:
            nx = b[i] + dx
            ny = a[i] + dy
            if nx < 1 or ny < 1 or\
                    nx+1 >= W or ny+1 >= H:
                continue
            elif (nx,ny) in used:
                continue
            else:
                ret = search(nx,ny,xs)
                ans[ret] += 1
                used.add((nx,ny))

ans[0] = (H-2)*(W-2) - len(used)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
grid = []
painted = []

height, width, n = sys.stdin.readline().strip().split()
height, width, n = int(height), int(width), int(n)

def checkGrid(x, y, grid):
    count = 0
    for col in range(x, x+3):
        for row in range(y, y+3):
            if grid[row][col] == 1:
                count += 1
    return count

inp = sys.stdin.readline().strip()
while inp:
    a, b = inp.split()
    grid.append([int(a) - 1, int(b) - 1])
    inp = sys.stdin.readline().strip()

# Build empty grid
for i in range(height):
    painted.append([])
    for j in range(width):
        if [i, j] in grid:
            painted[i].append(1)
        else:
            painted[i].append(0)

# Build painted cells
for cell in grid:
    painted[cell[0]][cell[1]] = 1

for i in range(0, 10):
    count = 0
    for col in range(width - 2):
        for row in range(height - 2):
            if checkGrid(col, row, painted) == i:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H, W, N = map(int, raw_input().split(' '))

T = Counter()

for _ in range(N):
    x, y = map(int, raw_input().split(' '))
    x -= 1
    y -= 1
    T[(x, y + 1)] += 1
    T[(x, y)] += 1
    T[(x, y - 1)] += 1
    T[(x-1,y+1)] += 1
    T[(x-1,y)] += 1
    T[(x-1,y-1)] += 1
    T[(x + 1, y + 1)] += 1
    T[(x + 1, y)] += 1
    T[(x + 1, y - 1)] += 1

ans = [0] * 10
total_points = H * W - (2 * H) - (2 * (W-2))
positive_points = 0
for (x, y), c in T.iteritems():
    if 0 < x < H-1 and 0 < y < W-1:
        ans[c] += 1
        positive_points += 1
ans[0] = total_points - positive_points

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

h,w,n=ii()
kuro=[[0,0] for j in range(n)]
for j in range(n):
    kuro[j]=ii()
ans=[0]*10
done=[]

for (x,y) in kuro:
    x-=1
    y-=1
    for (dx,dy) in itertools.product((-1,0,1), (-1,0,1)):
        if 0<x+dx<h-1 and 0<y+dy<w-1 and [x+dx,y+dy] not in done:
            done.append([x+dx,y+dy])
            cnt=0
            for (ddx,ddy) in itertools.product((-1,0,1), (-1,0,1)):
                if [x+dx+ddx+1,y+dy+ddy+1] in kuro:
                    cnt+=1
            ans[cnt]+=1

ans[0]+=(w-2)*(h-2)-sum(ans)
for j in range(10):
    print ans[j]

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
poss = [list(map(int, input().split())) for _ in range(N)]
d = defaultdict(int)
for a, b in poss:
    for i in range(a-1, a+2):
        for j in range(b-1, b+2):
            s = str(i)+":"+str(j)
            d[s] += 1
    #if 1<a<H and 1<b<W:
    #    d[str(a)+":"+str(b)] = count
def notedge(k):
    i, j = map(int, k.split(":"))
    if 1<i<H and 1<j<W:
        return True
    else:
        return False
d = {k:x for k, x in d.items() if notedge(k)}
anss = [sum(1 for k, x in d.items() if x==i) for i in range(1, 10)]
print((H-2)*(W-2) - sum(anss))
for ans in anss:
    print(ans)