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:
h,w,n = map(int,input().split())

blacks = [tuple(map(int,input().split())) for i in range(n)]
points = set(blacks)
squares = set()
cnts = [0]*10
def inbound(a,b):
    if a>h or a<=0 or b<=0 or b>w:
        return False
    else:
        return True

dxx = [-2,-1,0]
dyy = [-2,-1,0]

for x,y in blacks:
    for dx in dxx:
        for dy in dyy:
            xx = x + dx
            yy = y + dy
            if inbound(xx,yy) and inbound(xx+2,yy+2) and (xx,yy) not in squares:
                cnt = 0
                for i in range(3):
                    for j in range(3):
                        if (xx+i,yy+j) in points:
                            cnt+=1
                cnts[cnt]+=1
                squares.add((xx,yy))
cnts[0] = (h-2)*(w-2)-sum(cnts)
for c in cnts:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

from itertools import product

S = [set() for _ in range(10)]
N = [0]*10
N[0] = (H-2)*(W-2)
# S[i]: set(黒いマスをi個こ含む3*3マスの中心セル)

for a,b in AB:
  for x,y in product([-1,0,1], repeat=2):
    X = a+x-1
    Y = b+y-1
    if X<=0 or H-1<=X or Y<=0 or W-1<=Y:
      continue
    for i in range(10):
      if (X, Y) in S[i]:
        S[i].remove((X, Y))
        S[i+1].add((X, Y))
        N[i] -=1
        N[i+1] +=1
        break
    else:
      S[1].add((X, Y))
      N[1] +=1
      N[0] -=1

for n in N:
  print(n)

Submission status: Time Limit Exceeded

Solution code:
h, w, n = [int(item) for item in input().split()]
ab = [[int(item) for item in input().split()] for _ in range(n)]
poe = []
 
for a, b in ab:
    for i in range(3):
        for j in range(3):
            ah = a+i-1
            bw = b+j-1
            if ah > 1 and ah <= h-1 and bw > 1 and bw <= w-1:
                poe.append([ah, bw])
poe.sort()
 
ans = [0] * 10 
if len(poe) > 0:
    count = 1
    for i in range(1,len(poe)):
        if poe[i] == poe[i-1]:
            count += 1
        else:
            ans[count] += 1
            count = 1
    ans[count] += 1

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
  h,w,n = (int(i) for i in input().split())
  
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    d = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
    for dx,dy in d:
      if 2 <= a+dx <= h-1 and 2 <= b+dy <= w-1:
        query.append((a+dx,b+dy))
  ans = [0]*10
  #print(query)
  for i in range(2,h):
    for j in range(2,w):
      #print("aa",i,j)
      tp = query.count((i,j))
      #print(tp)
      ans[tp] += 1
  for i in ans:
    print(i)
solve()

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int, input().split())
hw = [list(map(int, input().split())) for q in range(n)]

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

for i in range(len(hw)):
    t[hw[i][0]-1][hw[i][1]-1] = 1

for j in range(1,h-1):
    for i in range(1,w-1):
        if i == 1:
            a = t[j-1][i-1] + t[j][i-1] + t[j+1][i-1]
            b = t[j-1][i] + t[j][i] + t[j+1][i]
            c = t[j-1][i+1] + t[j][i+1] + t[j+1][i+1]
            s.append(a+b+c)
        else:
            a = b
            b = c
            c = t[j-1][i+1] + t[j][i+1] + t[j+1][i+1]
            s.append(a+b+c)
    
for i in range(10):
    print(s.count(i))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, N] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    b_list = []
    b_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]) - 1, long(input_raw[1]) - 1]
        b_list.append((a, b))
        b_set.add((a, b))

    black_count = {}
    for i in range(10):
        black_count[i] = 0L

    already_set = set([])
    for m in b_list:
        for x in range(0, -3, -1):
            for y in range(0, -3, -1):
                square_upper_left_x = m[1] + x
                square_upper_left_y = m[0] + y
                if ((square_upper_left_y, square_upper_left_x) not in already_set and
                    square_upper_left_x + 2 < W and
                    square_upper_left_y + 2 < H and
                    square_upper_left_x >= 0 and
                    square_upper_left_y >= 0):
                        already_set.add((square_upper_left_y, square_upper_left_x))
                        count = 0
                        for i in range(3):
                            for j in range(3):
                                if (square_upper_left_y + j, square_upper_left_x + i) in b_set:
                                    count += 1
                        black_count[count] += 1L
    s = 0
    for i in range(1, 10):
        s += black_count[i]
    print (H -2) * (W - 2) - s
    for i in range(1, 10):
        print black_count[i]




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split())
c = set()
c2 = []
for i in range(n):#h:高さ
    c2.append([int(m) for m in input().split()])
for i in range(n):
    c2[i] = tuple(c2[i])
for i in range(n):
    c.add(c2[i])

vec = []
for i in range(-2, 3):
    for j in range(-2, 3):
        vec.append((i,j))
chuukai = []
for i in range(5):
    for j in range(5):
        chuukai.append([i, j])
#sq = {}
sq = [[0 for i in range(5)] for j in range(5)]
ansdi = [0]*10
chuukainum = 0
for i in range(n):
    for k in vec:
        if 0 < c2[i][0] + k[0] <= h and 0 < c2[i][1] + k[1] <= w:
            if (c2[i][0] + k[0], c2[i][1] + k[1]) in c:
                #sq[str(k[0]) + str(k[1])] = 1
                sq[chuukai[chuukainum][0]][chuukai[chuukainum][1]] = 1
        else:
            sq[chuukai[chuukainum][0]][chuukai[chuukainum][1]] = -1
        chuukainum += 1
    k1 = [sq[0][0], sq[0][1], sq[0][2],sq[1][0], sq[1][1], sq[1][2], sq[2][0], sq[2][1]].count(1) + 1
    l1 = [sq[0][0], sq[0][1], sq[0][2],sq[1][0], sq[1][1], sq[1][2], sq[2][0], sq[2][1]].count(-1)
    if l1 == 0:
        ansdi[k1] += 1
    k2 = [sq[0][3], sq[0][1], sq[0][2],sq[1][3], sq[1][1], sq[1][2], sq[2][3], sq[2][1]].count(1) + 1
    l2 = [sq[0][3], sq[0][1], sq[0][2],sq[1][3], sq[1][1], sq[1][2], sq[2][3], sq[2][1]].count(-1)
    if l2 == 0:
        ansdi[k2] += 1
    k3 = [sq[0][3], sq[0][4], sq[0][2],sq[1][3], sq[1][4], sq[1][2], sq[2][3], sq[2][4]].count(1) + 1
    l3 = [sq[0][3], sq[0][4], sq[0][2],sq[1][3], sq[1][4], sq[1][2], sq[2][3], sq[2][4]].count(-1)
    if l3 == 0:
        ansdi[k3] += 1
    k4 = [sq[3][0], sq[3][1], sq[3][2],sq[1][0], sq[1][1], sq[1][2], sq[2][0], sq[2][1]].count(1) + 1
    l4 = [sq[3][0], sq[3][1], sq[3][2],sq[1][0], sq[1][1], sq[1][2], sq[2][0], sq[2][1]].count(-1)
    if l4 == 0:
        ansdi[k4] += 1
    k5 = [sq[3][3], sq[3][1], sq[3][2],sq[1][3], sq[1][1], sq[1][2], sq[2][3], sq[2][1]].count(1) + 1
    l5 = [sq[3][3], sq[3][1], sq[3][2],sq[1][3], sq[1][1], sq[1][2], sq[2][3], sq[2][1]].count(-1)
    if l5 == 0:
        ansdi[k5] += 1
    k6 = [sq[3][3], sq[3][4], sq[3][2],sq[1][3], sq[1][4], sq[1][2], sq[2][3], sq[2][4]].count(1) + 1
    l6 = [sq[3][3], sq[3][4], sq[3][2],sq[1][3], sq[1][4], sq[1][2], sq[2][3], sq[2][4]].count(-1)
    if l6 == 0:
        ansdi[k6] += 1
    k7 = [sq[3][0], sq[3][1], sq[3][2],sq[4][0], sq[4][1], sq[4][2], sq[2][0], sq[2][1]].count(1) + 1
    l7 = [sq[3][0], sq[3][1], sq[3][2],sq[4][0], sq[4][1], sq[4][2], sq[2][0], sq[2][1]].count(-1)
    if l7 == 0:
        ansdi[k7] += 1
    k8 = [sq[3][3], sq[3][1], sq[3][2],sq[4][3], sq[4][1], sq[4][2], sq[2][3], sq[2][1]].count(1) + 1
    l8 = [sq[3][3], sq[3][1], sq[3][2],sq[4][3], sq[4][1], sq[4][2], sq[2][3], sq[2][1]].count(-1)
    if l8 == 0:
        ansdi[k8] += 1
    k9 = [sq[3][3], sq[3][4], sq[3][2],sq[4][3], sq[4][4], sq[4][2], sq[2][3], sq[2][4]].count(1) + 1
    l9 = [sq[3][3], sq[3][4], sq[3][2],sq[4][3], sq[4][4], sq[4][2], sq[2][3], sq[2][4]].count(-1)
    if l9 == 0:
        ansdi[k9] += 1
    sq = [[0 for i in range(5)] for j in range(5)]
    chuukainum = 0
for i in range(len(ansdi)):
    if i != 0:
        ansdi[i] = ansdi[i] // i
ansdi[0] = (h - 2) * (w - 2) - sum(ansdi)
for i in range(len(ansdi)):
    print(ansdi[i])

Submission status: Time Limit Exceeded

Solution code:
"""import time

if __name__ == '__main__':
    start = time.time()
    p = 0
    li = []
    y = []
    for i in range(0,3*10**6):
        li.append(i)
        y.append(i + 1)
        p += 1
    print(p)
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")"""
h, w, n = map(int, input().split())
c = set()
c2 = []
for i in range(n):#h:高さ
    c2.append([int(m) for m in input().split()])
for i in range(n):
    c2[i] = tuple(c2[i])
for i in range(n):
    c.add(c2[i])

vec = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if i != 0 or j != 0:
            vec.append((i,j))
sq = {}
ansdi = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0 , 6:0, 7:0, 8:0, 9:0}
for i in range(n):
    for k in vec:
        if 0 < c2[i][0] + k[0] <= h and 0 < c2[i][1] + k[1] <= w:
            if (c2[i][0] + k[0], c2[i][1] + k[1]) in c:
                sq[str(k[0]) + str(k[1])] = 1
            else:
                sq[str(k[0]) + str(k[1])] = 0
        else:
            sq[str(k[0]) + str(k[1])] = -1
    k1 = [sq["-2-2"], sq["-1-2"], sq["0-2"],sq["-2-1"], sq["-1-1"], sq["0-1"], sq["-20"], sq["-10"]].count(1) + 1
    l1 = [sq["-2-2"], sq["-1-2"], sq["0-2"],sq["-2-1"], sq["-1-1"], sq["0-1"], sq["-20"], sq["-10"]].count(-1)
    if l1 == 0:
        ansdi[k1] += 1
    k2 = [sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"], sq["-2-1"], sq["-1-1"], sq["0-1"]].count(1) + 1
    l2 = [sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"], sq["-2-1"], sq["-1-1"], sq["0-1"]].count(-1)
    if l2 == 0:
        ansdi[k2] += 1
    k3 = [sq["-22"], sq["-12"], sq["02"], sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"]].count(1) + 1
    l3 = [sq["-22"], sq["-12"], sq["02"], sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"]].count(-1)
    if l3 == 0:
        ansdi[k3] += 1
    k4 = [sq["-1-2"], sq["0-2"], sq["1-2"], sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"]].count(1) + 1
    l4 = [sq["-1-2"], sq["0-2"], sq["1-2"], sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"]].count(-1)
    if l4 == 0:
        ansdi[k4] += 1
    k5 = [sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"]].count(1) + 1
    l5 = [sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"]].count(-1)
    if l5 == 0:
        ansdi[k5] += 1
    k6 = [sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"], sq["-12"], sq["02"], sq["12"]].count(1) + 1
    l6 = [sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"], sq["-12"], sq["02"], sq["12"]].count(-1)
    if l6 == 0:
        ansdi[k6] += 1
    k7 = [sq["0-2"], sq["1-2"], sq["2-2"], sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"]].count(1) + 1
    l7 = [sq["0-2"], sq["1-2"], sq["2-2"], sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"]].count(-1)
    if l7 == 0:
        ansdi[k7] += 1
    k8 = [sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"], sq["01"], sq["11"], sq["21"]].count(1) + 1
    l8 = [sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"], sq["01"], sq["11"], sq["21"]].count(-1)
    if l8 == 0:
        ansdi[k8] += 1
    k9 = [sq["10"], sq["20"], sq["01"], sq["11"], sq["21"], sq["02"], sq["12"], sq["22"]].count(1) + 1
    l9 = [sq["10"], sq["20"], sq["01"], sq["11"], sq["21"], sq["02"], sq["12"], sq["22"]].count(-1)
    if l9 == 0:
        ansdi[k9] += 1
    sq = {}
for i in ansdi:
    if i != 0:
        ansdi[i] = ansdi[i] // i
ansdi[0] = (h - 2) * (w - 2) - sum(ansdi.values())
for i in ansdi:
    print(ansdi[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ans=[0 for i in range(10)]

data=[]
origin=[]
def check(a,b):
    if a>0 and a<H-1 and b>0 and b<W-1:return True
    else:return False

def count(a,b):
    for i in range(a-2,a+1):
        for j in range(b-2,b+1):
            if check(i,j):
                x=(i,j)
                data.append(x)
                if x not in origin:origin.append(x)
                
for k in range(N):
    a,b=map(int,input().split())
    count(a,b)

for x in origin:
    c = data.count(x)
    ans[c]+=1
zero = (H-2)*(W-2)-sum(ans)
ans[0]=zero
for i in range(10):
    print(ans[i])
    
#http://arc061.contest.atcoder.jp/data/arc/061/editorial.pdf

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
data=[[0 for i in range(W-2)] for j in range(H-2)]
def check(a,b):
    if a>1 and b>1:
        data[a-2][b-2]+=1
    if a>1 and b>0 and b<W-1:
        data[a-2][b-1]+=1
    if a>1 and b<W-2:
        data[a-2][b]+=1
    if a>0 and a<H-1 and b>1:
        data[a-1][b-2]+=1
    if a>0 and a<H-1 and b>0 and b<W-1:
        data[a-1][b-1]+=1
    if a>0 and a<H-1 and b<W-2:
        data[a-1][b]+=1
    if a<H-2 and b>1:
        data[a][b-2]+=1
    if a<H-2 and b>0 and b<W-1:
        data[a][b-1]+=1
    if a<H-2 and b<W-2:
        data[a][b]+=1
    return
for k in range(N):
    a,b=map(int,input().split())
    a-=1
    b-=1
    check(a,b)
for i in range(10):
    count=0
    for j in range(len(data)):
        count+=data[j].count(i)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
ab = []
for i in range(N):
    a, b = map(int, input().split())
    ab.append((a - 1, b - 1))

comb_map = {}
if N >= 1:
    for i in range(0, H - 2):
        for j in range(0, W - 2):
            comb_map[(i, j)] = 0

    for a, b in ab:
        for k in range(3):
            for m in range(3):
                if 0 <= a - k < H - 2 and 0 <= b - m < W - 2:
                    comb_map[(a - k, b - m)] += 1

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

for v in comb_map.values():
    count[v] += 1

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

for c in count:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
"""import time

if __name__ == '__main__':
    start = time.time()
    p = 0
    li = []
    y = []
    for i in range(0,3*10**6):
        li.append(i)
        y.append(i + 1)
        p += 1
    print(p)
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")"""
h, w, n = map(int, input().split())
c = set()
c2 = []
for i in range(n):#h:高さ
    c2.append([int(m) for m in input().split()])
for i in range(n):
    c2[i] = tuple(c2[i])
for i in range(n):
    c.add(c2[i])

vec = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if i != 0 or j != 0:
            vec.append((i,j))
sq = {}
ansdi = {0:0, 1:0, 2:0, 3:0, 4:0, 5:0 , 6:0, 7:0, 8:0, 9:0}
for i in range(n):
    for k in vec:
        if 0 < c2[i][0] + k[0] <= h and 0 < c2[i][1] + k[1] <= w:
            if (c2[i][0] + k[0], c2[i][1] + k[1]) in c:
                sq[str(k[0]) + str(k[1])] = 1
            else:
                sq[str(k[0]) + str(k[1])] = 0
        else:
            sq[str(k[0]) + str(k[1])] = -1
    k1 = [sq["-2-2"], sq["-1-2"], sq["0-2"],sq["-2-1"], sq["-1-1"], sq["0-1"], sq["-20"], sq["-10"]].count(1) + 1
    l1 = [sq["-2-2"], sq["-1-2"], sq["0-2"],sq["-2-1"], sq["-1-1"], sq["0-1"], sq["-20"], sq["-10"]].count(-1)
    if l1 == 0:
        ansdi[k1] += 1
    k2 = [sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"], sq["-2-1"], sq["-1-1"], sq["0-1"]].count(1) + 1
    l2 = [sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"], sq["-2-1"], sq["-1-1"], sq["0-1"]].count(-1)
    if l2 == 0:
        ansdi[k2] += 1
    k3 = [sq["-22"], sq["-12"], sq["02"], sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"]].count(1) + 1
    l3 = [sq["-22"], sq["-12"], sq["02"], sq["-21"], sq["-11"], sq["01"], sq["-20"], sq["-10"]].count(-1)
    if l3 == 0:
        ansdi[k3] += 1
    k4 = [sq["-1-2"], sq["0-2"], sq["1-2"], sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"]].count(1) + 1
    l4 = [sq["-1-2"], sq["0-2"], sq["1-2"], sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"]].count(-1)
    if l4 == 0:
        ansdi[k4] += 1
    k5 = [sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"]].count(1) + 1
    l5 = [sq["-1-1"], sq["0-1"], sq["1-1"], sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"]].count(-1)
    if l5 == 0:
        ansdi[k5] += 1
    k6 = [sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"], sq["-12"], sq["02"], sq["12"]].count(1) + 1
    l6 = [sq["-10"], sq["10"], sq["-11"], sq["01"], sq["11"], sq["-12"], sq["02"], sq["12"]].count(-1)
    if l6 == 0:
        ansdi[k6] += 1
    k7 = [sq["0-2"], sq["1-2"], sq["2-2"], sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"]].count(1) + 1
    l7 = [sq["0-2"], sq["1-2"], sq["2-2"], sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"]].count(-1)
    if l7 == 0:
        ansdi[k7] += 1
    k8 = [sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"], sq["01"], sq["11"], sq["21"]].count(1) + 1
    l8 = [sq["0-1"], sq["1-1"], sq["2-1"], sq["10"], sq["20"], sq["01"], sq["11"], sq["21"]].count(-1)
    if l8 == 0:
        ansdi[k8] += 1
    k9 = [sq["10"], sq["20"], sq["01"], sq["11"], sq["21"], sq["02"], sq["12"], sq["22"]].count(1) + 1
    l9 = [sq["10"], sq["20"], sq["01"], sq["11"], sq["21"], sq["02"], sq["12"], sq["22"]].count(-1)
    if l9 == 0:
        ansdi[k9] += 1
    sq = {}
for i in ansdi:
    if i != 0:
        ansdi[i] = ansdi[i] // i
ansdi[0] = (h - 2) * (w - 2) - sum(ansdi.values())
for i in ansdi:
    print(ansdi[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
x,y,z=map(int,input().split(" "))
a=[tuple(map(int,input().split(" "))) for _ in range(z)]
b=[[0 for i in range(y)] for j in range(x)]
d={}
for i in range(10):
    d["{}".format(i)]="0"
for j,k in a:
    b[j-1][k-1]=1
for i in range(x-2):
    for j in range(y-2):
        e=np.array([[b[i][j],b[i][j+1],b[i][j+2]],[b[i+1][j],b[i+1][j+1],b[i+1][j+2]],[b[i+2][j],b[i+2][j+1],b[i+2][j+2]]])
        c=np.sum(e)
        d[str(c)]=str(int(d[str(c)])+1)
for i in range(10):
    print(d["{}".format(i)])

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split(" ")))
ar = [["w" for i in range(a[1])] for j in range(a[0])]
arr = {}
for i in range(10):
    arr[str(i)] = 0
for j in range(a[2]):
    l = list(map(int,input().split(" ")))
    ar[l[0]-1][l[1]-1] = "b"
count = 0
for k in range(a[1]-2):
    for l in range(a[0]-2):
        if ar[l][k] == "b":
            count += 1
        if ar[l+1][k] == "b":
            count += 1
        if ar[l+2][k] == "b":
            count += 1
        if ar[l][k+1] == "b":
            count += 1
        if ar[l+1][k+1] == "b":
            count += 1
        if ar[l+2][k+1] == "b":
            count += 1
        if ar[l][k+2] == "b":
            count += 1
        if ar[l+1][k+2] == "b":
            count += 1
        if ar[l+2][k+2] == "b":
            count += 1
        arr[str(count)] += 1
        count = 0
for i in range(10):
    print(arr[str(i)])

Submission status: Time Limit Exceeded

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

h, w, n = map(int, sdin().split())
ab = []
for _ in range(n):
    ab.append(tuple(map(int, sdin().split())))
    
# フィールドを作って塗る
field = [[0 for _ in range(w+1)] for _ in range(h+1)]

x = [-1,-1,-1, 0, 0, 0, 1, 1, 1]
y = [-1, 0, 1,-1, 0, 1,-1, 0, 1]

for a, b in ab:
    for dx,dy in zip(x, y):
        if a+dx > 0 and a+dx <= h and b+dy > 0 and b+dy <= w:
            field[a+dx][b+dy] += 1
            
# 数え上げる
for j in range(10):
    row = [field[r][2:w].count(j) for r in range(2,h)]
    print(sum(row))

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
A = []
for i in range(N):
  a, b = map(int, input().split())
  for j in range(3):
    for k in range(3):
      if (a - j > 0) and (a - j < H - 1) and (b - k > 0) and (b - k < W - 1):
        A.append([a - j, b - k])
A = sorted(sorted(A, key=lambda x: x[1]), key=lambda x: x[0])
A.append([0, 0])
prev = [0, 0]
count = 0
C = [0 for i in range(10)]
for a in A:
  if a == prev:
    count += 1
  else:
    C[count] += 1
    count = 1
  prev = a
print((H - 2) * (W - 2) - sum(C[1:]))
for c in C[1:]:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
A = []
for i in range(N):
  a, b = map(int, input().split())
  for j in range(3):
    for k in range(3):
      if (a - j > 0) and (a - j < H - 1) and (b - k > 0) and (b - k < W - 1):
        A.append([a - j, b - k])
A = sorted(sorted(A, key=lambda x: x[1]), key=lambda x: x[0])
A.append([0, 0])
prev = [0, 0]
count = 0
C = [0 for i in range(10)]
for a in A:
  if a[0] == prev[0] and a[1] == prev[1]:
    count += 1
  else:
    C[count] += 1
    count = 1
  prev = a
print((H - 2) * (W - 2) - sum(C[1:]))
for c in C[1:]:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
G = [[0 for w in range(W)] for h in range(H)]
for i in range(N):
  a, b = map(int, input().split())
  for j in range(3):
    for k in range(3):
      if (a - j > 0) and (b - k > 0):
        G[a - j - 1][b - k - 1] += 1
A = [0 for i in range(10)]
for h in range(H - 2):
  for w in range(W - 2):
    A[G[h][w]] += 1
for a in A:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
cm=[[0 for i in range(0,w)] for j in range(0,h)]

def nextcell(x,y):
    a=[[x-1,y-1],[x-1,y],[x-1,y+1],[x,y-1],[x,y],[x,y+1],[x+1,y-1],[x+1,y],[x+1,y+1]]
    if x==0:
        if y==0:
            a.remove([x-1,y-1])
            a.remove([x-1,y])
            a.remove([x-1,y+1])
            a.remove([x,y-1])
            a.remove([x+1,y-1])
        elif y==w-1:
            a.remove([x-1,y-1])
            a.remove([x-1,y])
            a.remove([x-1,y+1])
            a.remove([x,y+1])
            a.remove([x+1,y+1])
        else:
            a.remove([x-1,y-1])
            a.remove([x-1,y])
            a.remove([x-1,y+1])
    if y==0:
        if x==h-1:
            a.remove([x+1,y-1])
            a.remove([x+1,y])
            a.remove([x+1,y+1])
            a.remove([x,y-1])
            a.remove([x-1,y-1])
        elif x!=0:
            a.remove([x-1,y-1])
            a.remove([x,y-1])
            a.remove([x+1,y-1])
    if y==w-1:
        if x==h-1:
            a.remove([x+1,y-1])
            a.remove([x+1,y])
            a.remove([x+1,y+1])
            a.remove([x,y+1])
            a.remove([x-1,y+1])
        elif x!=0:
            a.remove([x+1,y+1])
            a.remove([x,y+1])
            a.remove([x-1,y+1])
    if x==h-1:
        if y!=0 and y!=w-1:
            a.remove([x+1,y-1])
            a.remove([x+1,y])
            a.remove([x+1,y+1])
    return a        

for i in range(n):
    a,b=map(int,input().split())
    for j in nextcell(a-1,b-1):
        if len(nextcell(j[0],j[1]))==9:
            cm[j[0]][j[1]]+=1
s=0
for j in cm:
        s+=j.count(0)
print(s-2*(h-1+w-1))
for i in range(1,10):
    s=0
    for j in cm:
        s+=j.count(i)
    print(s)

Submission status: Time Limit Exceeded

Solution code:
hwn=list(map(int,input().split()))
cm=[[0 for i in range(hwn[1])] for j in range(hwn[0])]
cl=[]
for k in range(hwn[2]):
    a=list(map(int,input().split()))
    cm[a[0]-1][a[1]-1]=1
for l in range(1,hwn[0]-1):
    for m in range(1,hwn[1]-1):
        c=cm[l-1][m-1]+cm[l-1][m]+cm[l-1][m+1]+cm[l][m-1]+cm[l][m]+cm[l][m+1]+cm[l+1][m-1]+cm[l+1][m]+cm[l+1][m+1]
        cl.append(c)
        c=0
for i in range(10):
    print(cl.count(i))

Submission status: Time Limit Exceeded

Solution code:
h,w,n = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
def sq(a,b,h,w):
	A,B,X = [a-2,a-1,a],[b-2,b-1,b],[]
	for i in A:
		for j in B:
			if 1<=i<=h-2 and 1<=j<=w-2: X.append([i,j])
	return X
y,ans = [],[0 for i in range(10)]
for i,j in x: y += sq(i,j,h,w)
y,i,num = sorted(y),0,1
while y!=[]:
	if y[i]==y[i+1]: num+=1
	else: ans[num],num = ans[num]+1,1
	if i==len(y)-2:
		ans[num]+=1
		break
	else: i+=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())
a = [None] * n
s = set()
for i in range(n):
    y, x = map(int, input().split())
    a[i] = (y - 1, x - 1)
    s.add((y -1 , x - 1))
t = set()
e = [0] * 10
c = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
d = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
for i in range(n):
    y, x = a[i]
    for j in range(9):
        y2 = y + c[j]
        x2 = x + d[j]
        if y2 <= 0 or x2 <= 0 or y2 >= h - 1 or x2 >= w - 1: continue
        z = 0
        if (y2, x2) in t: continue
        t.add((y2, x2))
        for k in range(9):
            y3 = y2 + c[k]
            x3 = x2 + d[k]
            if (y3, x3) in s: z += 1
        e[z] += 1
print(((h - 2) * (w - 2)) - sum(e))
for i in range(1, 10): print(e[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

XY=[]
ND=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]]

M=defaultdict(int)
for i in range(N):
  a,b=map(int,input().split())
  XY.append([a-1,b-1])
  for c,d in ND:
    if 1 <= a-1+c < H-1 and 1 <= b-1+d < W-1:
      M[(a-1+c,b-1+d)]+=1

dict={1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
cnt=0
for a,b in XY:
  for c,d in ND:
    if 1 <= a+c < H-1 and 1 <= b+d < W-1 and M[(a+c,b+d)]>=0:
      dict[M[(a+c,b+d)]]+=1
      M[(a+c,b+d)]=-1
      cnt+=1
ans=(H-2)*(W-2)-cnt
print(ans)
for i in range(1,10):
  print(dict[i])

Submission status: Time Limit Exceeded

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

d=[-1,0,1]
D=list(itertools.product(d,d))

C=set()	#Center
A=defaultdict(lambda: 0)
for i in range(N):
	a,b=map(int, raw_input().split())
	A[(a,b)]=1
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			C.add( (cx,cy) )

l=defaultdict(lambda: 0)

for x,y in C:
	cnt=0
	for i,j in D:
		if A[(x+i,y+j)]==1:
			cnt+=1
	l[cnt]+=1



for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(l.values())
	else:
		print l[i]

Submission status: Time Limit Exceeded

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

d=[-1,0,1]
D=list(itertools.product(d,d))

C=set()	#Center
A=[]
for i in range(N):
	a,b=map(int, raw_input().split())
	A.append((a,b))
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			C.add( (cx,cy) )



l=defaultdict(lambda: 0)

for x,y in C:
	cnt=0
	for i,j in D:
		#print x+i,y+j,A[x+i][y+j]
		if (x+i, y+j) in A:
			cnt+=1
	l[cnt]+=1



for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(l.values())
	else:
		print l[i]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ss = set()
for i in range(n):
    a, b = map(int, input().split())
    ss.add((a-1, b-1))

ret = np.array([0] * 10)

for dot in ss:
    x = dot[0]
    y = dot[1]
    for x in [-2, -1, 0]:
        x += dot[0]
        if x < 0 or h <= x + 2:
            continue
        for y in [-2, -1, 0]:
            y += dot[1]
            if y < 0 or w <= y + 2:
                continue
            tmp_sum = 0
            for i in range(3):
                if h <= x + i:
                    continue
                for j in range(3):
                    if w <= y + j:
                        continue
                    if (x + i, y + j) in ss:
                        tmp_sum += 1
            ret[tmp_sum] += 1

ret2 = [int(tmp / i) for i, tmp in enumerate(ret) if i]
print(int((h - 2) * (w - 2) - sum(ret2)))
[print(int(tmp)) for tmp in ret2]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc045/tasks/arc061_b

"""
import sys
from sys import stdin
from collections import defaultdict
from copy import copy
input = stdin.readline


def solve(H, W, N, points):
    ans = [0] * 10              #  3x3のうちマスがi個だけ黒いパタンの数
    checked = set()
    ccc = copy(points)

    for k, v in points.items():
        for x, y in v:
            for xx in [-2, -1, 0]:
                for yy in [-2, -1, 0]:
                    lbx = x + xx
                    lby = y + yy
                    if (lbx, lby) not in checked:
                        checked.add((lbx, lby))
                        if 1 <= lbx and lbx+2 <= W and 1 <= lby and lby+2 <= H:
                            res = 0
                            for ddx in [0, 1, 2]:
                                t = ccc[lbx + ddx]
                                if (lbx + ddx, lby) in t:
                                    res += 1
                                if (lbx + ddx, lby + 1) in t:
                                    res += 1
                                if (lbx + ddx, lby + 2) in t:
                                    res += 1
                            ans[res] += 1

    total = (W-2) * (H-2)         #  3x3の正方形の全パタン
    ans[0] = total - sum(ans[1:]) #  1マスも塗られていないのは、全パタン数-一つでも塗ってあるパタン数
    return ans


def main(args):
    points = defaultdict(set)

    H, W, N = map(int, input().split())
    for _ in range(N):
        y, x = map(int, input().split())
        points[x].add((x, y))

    ans = solve(H, W, N, points)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])