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:
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(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()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
d = defaultdict(int)

dp = [0] * 10
dp[0] = (h - 2) * (w - 2)
for i in range(n):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            nx, ny = a + dx, b + dy # center
            if nx >= 1 and nx <= h - 2 and ny >= 1 and ny <= w - 2:
                # print(nx, ny)
                tmp = 0
                for dx2 in [-1, 0, 1]:
                    for dy2 in [-1, 0, 1]:
                        if d[str(nx + dx2) + ' ' + str(ny + dy2)] == 1:
                            tmp += 1

                dp[tmp] -= 1
                dp[tmp + 1] += 1
    d[str(a) + ' ' + str(b)] = 1
    # print(dp)

for d in dp:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split(' '))
p = []
for i in range(n):
    ta, tb = map(int, input().split(' '))
    p.append((ta - 1, tb - 1))

cache = {}
result = {}
for i in range(10):
    result[i] = 0

for i in range(n):
    for dh in range(-1, 2):
        for dw in range(-1, 2):
            gh = p[i][0] + dh
            gw = p[i][1] + dw
            if gh - 1 < 0 or gh >= h - 1:
                continue
            if gw - 1 < 0 or gw >= w - 1:
                continue
            if (gh, gw) in cache:
                continue
            count = sum(p.count((gh + ih, gw + iw)) for ih in range(-1, 2) for iw in range(-1, 2))
            cache[(gh, gw)] = count
            result[count] += 1

result[0] = (h - 2) * (w - 2) - sum(result[i] for i in range(1, 10))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from itertools import groupby,product
def resolve():
    h,w,n=map(int,input().split())
    S=[]
    for _ in range(n):
        a,b=map(int,input().split())
        for i,j in product(range(a-1,a+2),range(b-1,b+2)):
            if(2<=i<=h-1 and 2<=j<=w-1):
                S.append((i,j))
    S.sort()

    ans=[0]*10
    for key,iter in groupby(S):
        ans[len(tuple(iter))]+=1
    ans[0]=(h-2)*(w-2)-sum(ans)
    print(*ans,sep='\n')
resolve()

Submission status: Time Limit Exceeded

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

k=[0]*10
for j in range(h-2):
  for f in range(w-2):
    k[s[j][f]+s[j][f+1]+s[j][f+2]+s[j+1][f]+s[j+1][f+1]+s[j+1][f+2]+s[j+2][f]+s[j+2][f+1]+s[j+2][f+2]]+=1
for i in range(10):
  print(k[i])

Submission status: Time Limit Exceeded

Solution code:
def examD():
    H, W, N = LI()
    ab = set()
    for _ in range(N):
        a, b = list(map(int,input().split()))
        ab.add((a-1,b-1))
    check = set()
    for c in ab:
        for i in range(-1,2):
            for j in range(-1,2):
                if 1<=c[0]+i<H-1 and 1<=c[1]+j<W-1:
                    check.add((c[0]+i,c[1]+j))
#    print(check)
#    print(ab)
    ansC = [0]*10
    for c in check:
        cur = int(0)
        for i in range(-1,2):
            for j in range(-1,2):
                if (c[0]+i,c[1]+j) in ab:
                    cur += 1
        ansC[cur] +=1
    ansC[0] = (H-2)*(W-2)-sum(ansC)
    for v in ansC:
        print(v)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve():
    H, W, N = list(map(int, input().split()))
    # print(H, W, N)

    # 座標は(y, x)
    blacks = {}
    for _ in range(N):
        pos = input().split()
        blacks[(int(pos[0]), int(pos[1]))] = 0

    # print(blacks)

    # [*][*][*]
    # [*][c][*]
    # [*][*][*]
    # ある座標から, それを中心にした9つの座標を返す
    def center_of_boxes_from_point(y, x):
        center_pos_lis = deque()

        for dy in range(-1, 2):
            for dx in range(-1, 2):
                cy = y + dy
                cx = x + dx
                if 1 <= cy <= H and 1 <= cx <= W:
                    center_pos_lis.append((cy, cx))
        return center_pos_lis

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

    # 探索を終了したboxを保存する
    # keyはboxの中心の座標
    done_boxes = {}
    for blk in blacks:
        # print(blk)
        y, x = blk
        boxes = center_of_boxes_from_point(y, x)

        # boxを探索して黒マスをカウントする
        for center_of_box in boxes:
            if center_of_box not in done_boxes:
                y, x = center_of_box
                if 2 <= y < H and 2 <= x < W:
                    count = 0
                    for dy in range(-1, 2):
                        for dx in range(-1, 2):
                            cy = y + dy
                            cx = x + dx
                            if (cy, cx) in blacks:
                                count += 1
                    # print(center_of_box, count)
                    ANS_TABLE[count] += 1
                    done_boxes[center_of_box] = 0

    # print('total boxes', (W - 2) * (H - 2))
    ANS_TABLE[0] = (W - 2) * (H - 2) - sum(ANS_TABLE)

    return ANS_TABLE


if __name__ == '__main__':
    res = solve()
    for r in res:
        print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np


def solve():
    H, W, N = map(int, input().split())
    # print("H, W", H, W)
    # print("N", N)

    blacks = deque()
    for _ in range(N):
        blacks.append(tuple(map(int, input().split())))

    TABLE = deque()
    for _ in range(H + 1):
        TABLE.append(0)

    dx = W
    for pos in blacks:
        x = dx - pos[1]
        y = pos[0]
        # print(y, x)
        TABLE[y] = TABLE[y] | 2**x

    RES_TABLE = [0 for _ in range(10)]
    fLAG_DICT = {0: 0, 1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 2, 7: 3}
    for y in range(1, H + 1, 1):
        if y + 2 > H:
            break

        lis = []
        top_middle_bottom = []
        for y2 in range(y, y + 3):
            line = TABLE[y2]
            lines = []
            for head in range(W - 1, -1, -1):
                tail = (head - 2)
                if tail >= 0:
                    key = line >> tail & 0b111
                    lines.append(fLAG_DICT[key])
            top_middle_bottom.append(np.array(lines))

        total = sum(top_middle_bottom)
        for t in total:
            RES_TABLE[t] += 1

    return RES_TABLE


if __name__ == '__main__':
    res = solve()
    for lis in res:
        print(lis)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W,N = map(int,input().split())
count = []
L = 0
for i in range(N):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(max(0,a-2),min(a+1,H-2)):
        for j in range(max(0,b-2),min(b+1,W-2)):
            count.append((i,j))
            L += 1
count.sort()
ans = [0]*10
tmp = 1
for i in range(L-1):
    if count[i] == count[i+1]:
        tmp += 1
    else:
        ans[tmp] += 1
        tmp = 1
if L>=1:
  ans[tmp] += 1
ans[0] = (H-2)*(W-2)-sum(ans)
for i in range(10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
if N == 0:
  print((H-2)*(W-2))
  for i in range(9):
    print(0)
  exit()

AB = [list(map(int,input().split())) for _ in range(N)]

Board = [[0 for _ in range(W)] for _ in range(H)]
Cell = []
Count = [0 for _ in range(10)]

for a,b in AB:
  a -= 1
  b -= 1
  Board[a][b] = 1
  for i in range(-1,2):
    for j in range(-1,2):
      if 1 <= a+i <= H-2 and 1 <= b+j <= W-2:
        Cell.append([a+i,b+j])
Cell.sort(key=lambda x:(x[0],x[1]))
#print(Board)
#print(Cell)
prea = 0
preb = 0
for a,b in Cell:
  if a == prea and b == preb:
    continue
  c = 0
  for k in range(-1,2):
    for l in range(-1,2):
      c += Board[a+k][b+l]
  Count[c] += 1
  prea = a
  preb = b

Count[0] = (H-2)*(W-2)-sum(Count[1:])
for c in Count:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
if N == 0:
  print((H-2)*(W-2))
  for i in range(9):
    print(0)
  exit()

AB = [list(map(int,input().split())) for _ in range(N)]

Board = [[0 for _ in range(W)] for _ in range(H)]
Cell = set()
Count = [0 for _ in range(10)]


for a,b in AB:
  a -= 1
  b -= 1
  Board[a][b] = 1
  for i in range(-1,2):
    for j in range(-1,2):
      if 1 <= a+i <= H-2 and 1 <= b+j <= W-2:
        Cell.add((a+i,b+j))
#print(Board)
#print(Cell)
for a,b in Cell:
  c = 0
  for k in range(-1,2):
    for l in range(-1,2):
      c += Board[a+k][b+l]
  Count[c] += 1
Count[0] = (H-2)*(W-2)-sum(Count[1:])
for c in Count:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int,input().split())
if N == 0:
  print((H-2)*(W-2))
  for i in range(9):
    print(0)
  exit()

AB = [list(map(int,input().split())) for _ in range(N)]

Board = [[0 for _ in range(W)] for _ in range(H)]
Done = [[0 for _ in range(W)] for _ in range(H)]
Count = [0 for _ in range(10)]

for a,b in AB:
  Board[a-1][b-1] = 1
for a,b in AB:
  a -= 1
  b -= 1
  for i in range(-1,2):
    for j in range(-1,2):
      if 1 <= a+i <= H-2 and 1 <= b+j <= W-2:
        if Done[a+i][b+j] == 1:
          continue
        c = 0
        for k in range(-1,2):
          for l in range(-1,2):
            c += Board[a+i+k][b+j+l]
        Count[c] += 1
        Done[a+i][b+j] = 1
Count[0] = (H-2)*(W-2)-sum(Count[1:])
for c in Count:
  print(c)

Submission status: Time Limit Exceeded

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

A = [None] * N
B = [None] * N

M = {}
R = [0] * 10
Q = set([])

if N > 0:
    for n in range(N):
        a, b       = map(int, input().split())
        A[n], B[n] = a, b
        if not a in M:
            M[a] = (b, )
        else:
            M[a] = M[a] + (b, )

    for n in range(N):
        a, b  = A[n], B[n]
        Q_tmp = [(p, q) for p in [a-2, a-1, a] for q in [b-2, b-1, b] if 1 <= p and p <= H-2 and 1 <= q and q <= W-2]
        for q_tmp in Q_tmp:
            Q.add(q_tmp)

    for q in Q:
        r = 0
        for a, b in [(q[0], q[1]), (q[0], q[1]+1), (q[0], q[1]+2), (q[0]+1, q[1]), (q[0]+1, q[1]+1), (q[0]+1, q[1]+2), (q[0]+2, q[1]), (q[0]+2, q[1]+1), (q[0]+2, q[1]+2)]:
            try:
                r += int(b in M[a])
            except:
                pass
        R[r] += 1

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

for r in R:
    print(r)

Submission status: Time Limit Exceeded

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

A = [None] * N
B = [None] * N

M = {}
R = [0] * 10
Q = set([])

if N > 0:
    for n in range(N):
        a, b       = map(int, input().split())
        A[n], B[n] = a, b
        if not a in M:
            M[a] = (b, )
        else:
            M[a] = M[a] + (b, )

    zipped = zip(A, B)
    zipped = sorted(zipped, key=lambda x: [x[0], x[1]], reverse=False)
    A, B   = map(list, zip(*zipped))

    for n in range(N):
        a, b  = A[n], B[n]
        Q_tmp = [(p, q) for p in [a-2, a-1, a] for q in [b-2, b-1, b] if 1 <= p and p <= H-2 and 1 <= q and q <= W-2]
        for q_tmp in Q_tmp:
            Q.add(q_tmp)

    for q in Q:
        r = 0
        for a, b in [(q[0], q[1]), (q[0], q[1]+1), (q[0], q[1]+2), (q[0]+1, q[1]), (q[0]+1, q[1]+1), (q[0]+1, q[1]+2), (q[0]+2, q[1]), (q[0]+2, q[1]+1), (q[0]+2, q[1]+2)]:
            try:
                r += int(b in M[a])
            except:
                pass
        R[r] += 1

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

for r in R:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w, n = map(int, input().split())
pos = collections.defaultdict(lambda: collections.defaultdict(bool))
squares = collections.defaultdict(lambda: collections.defaultdict(bool))
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pos[a][b] = True
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares[y][x] = True
counter = collections.Counter()
for y, xs in squares.items():
    for x in xs:
        count = 0
        for i in range(3):
            for j in range(3):
                if pos[y + i][x + j]:
                    count += 1
        counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w, n = map(int, input().split())
pos = collections.defaultdict(lambda: collections.defaultdict(bool))
squares = set()
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pos[a][b] = True
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares.add((y, x))
counter = collections.Counter()
for y, x in squares:
    count = 0
    for i in range(3):
        for j in range(3):
            if pos[y + i][x + j]:
                count += 1
    counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])

Submission status: Time Limit Exceeded

Solution code:
inp=input().split(" ")
H=int(inp[0])
W=int(inp[1])
N=int(inp[2])
square=[]
plot=[]
times=[0 for i in range(10)]
times[0]=(H-2)*(W-2)
from collections import defaultdict
count=defaultdict(lambda:0)
def check(a,b,square):
    for i in range(3):
        for j in range(3):
            if a-i>=0 and b-j>=0 and a+2-i<=H-1 and b+2-j<=W-1:
                square.append([a-i,b-j])
for i in range(N):
    plot.append(list(map(int,input().split(" "))))
    check(plot[i][0]-1,plot[i][1]-1,square)
for i in range(len(square)):
    count[str(square[i])]+=1
for i in count.values():
    times[i]+=1
    times[0]-=1
for i in range(len(times)):
    print(times[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
H, W, N = map(int, input().split())

board = defaultdict(int)
black = []
for _ in range(N):
    a, b = map(int, input().split())
    black.append((a - 1, b - 1))
    board[(a-1) * 10 ** 10 + (b - 1)] = 1

num = [0] * 10
for p in black:
    for ch in range(max(p[0] - 1, 1), min(p[0] + 2, H - 1)):
        for cw in range(max(p[1] - 1, 1), min(p[1] + 2, W - 1)):
            count = 0
            for h in range(ch - 1, ch + 2):
                for w in range(cw - 1, cw + 2):
                    if board[h * 10 ** 10 + w] == 1:
                        count += 1
            num[count] += 1
for i in range(1, 10):
    num[i] //= i
print((H - 2) * (W - 2) - sum(num))
for i in range(1, 10):
    print(num[i])

Submission status: Time Limit Exceeded

Solution code:

def main():
    input = open(0).readline
    H, W, N = map(int, input().split())
    grid = {}
    AB = [0]*N
    for i in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        AB[i] = a, b
        grid[(a,b)]=1

    total = ((H-3)+1)*((W-3)+1)
    count = [0] * 10
    offset = [-2, -1, 0]
    for a, b in AB:
        for x in offset:
            ax = a+x
            if not (0 <= ax and ax+2 < H):
                continue
            for y in offset:
                by = b + y
                if 0 <= by and by+2 < W:
                    c = sum(grid.get((ax+i, by+j),0)
                            for i in range(3)
                            for j in range(3))
                    count[c] += 1

    for i in range(1, 10):
        count[i] //= i

    print(total-sum(count))
    for i in range(1, 10):
        #print(i, len(count[i])//i)#, count[i])
        print(count[i])#, count[i])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, N = map(int, input().split())
    grid = set()
    for i in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        grid.add((a,b))

    total = ((H-3)+1)*((W-3)+1)
    count = [0] * 10
    offset = [-2, -1, 0]
    for a, b in grid:
        for x in offset:
            ax = a+x
            if not (0 <= ax and ax+2 < H):
                continue
            for y in offset:
                by = b + y
                if 0 <= by and by+2 < W:
                    c = sum(1 if (ax+i, by+j) in grid else 0 for i in range(3)
                        for j in range(3))
                    count[c] += 1

    for i in range(1, 10):
        count[i] //= i

    print(total-sum(count))
    for i in range(1, 10):
        #print(i, len(count[i])//i)#, count[i])
        print(count[i])#, count[i])
main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    input = open(0).readline
    H, W, N = map(int, input().split())
    grid = set()
    for i in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        grid.add((a,b))

    total = ((H-3)+1)*((W-3)+1)
    count = [0] * 10
    offset = [-2, -1, 0]
    for a, b in grid:
        for x in [-2, -1, 0]:
            ax = a+x
            if not (0 <= ax and ax+2 < H):
                continue
            for y in [-2, -1, 0]:
                by = b + y
                if 0 <= by and by+2 < W:
                    c = sum(1 if (ax+i, by+j) in grid else 0 for i in range(3)
                        for j in range(3))
                    count[c] += 1

    for i in range(1, 10):
        count[i] //= i

    print(total-sum(count))
    for i in range(1, 10):
        #print(i, len(count[i])//i)#, count[i])
        print(count[i])#, count[i])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, N = map(int, input().split())
    grid = set()
    for i in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        grid.add((a,b))

    total = ((H-3)+1)*((W-3)+1)
    count = [0] * 10
    offset = [-2, -1, 0]
    for a, b in grid:
        for x in [-2, -1, 0]:
            ax = a+x
            if not (0 <= ax and ax+2 < H):
                continue
            for y in [-2, -1, 0]:
                by = b + y
                if 0 <= by and by+2 < W:
                    c = sum(1 if (ax+i, by+j) in grid else 0 for i in range(3)
                        for j in range(3))
                    count[c] += 1

    for i in range(1, 10):
        count[i] //= i

    print(total-sum(count))
    for i in range(1, 10):
        #print(i, len(count[i])//i)#, count[i])
        print(count[i])#, count[i])
main()

Submission status: Time Limit Exceeded

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

grid = set()

for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    grid.add((a,b))

total = ((H-3)+1)*((W-3)+1)
#count = [[] for i in range(10)]
count = [0] * 10
for a, b in grid:
    for x in [-2, -1, 0]:
        for y in [-2, -1, 0]:
            c = 0
            if 0 <= a+x and a+x+2 < H and 0 <= b+y and b+y+2 < W:
                for i in range(3):
                    for j in range(3):
                        c += 1 if (a+x+i, b+y+j) in grid else 0
                #count[c].append((a+1,b+1))
                count[c] += 1
for i in range(1, 10):
    count[i] //= i

print(total-sum(count))
for i in range(1, 10):
    #print(i, len(count[i])//i)#, count[i])
    print(count[i])#, count[i])

Submission status: Time Limit Exceeded

Solution code:
H, W, N = list(map(int, input().split(' ')))
ab = [list(map(int, input().split(' '))) for i in range(N)]
#print(ab)

#field = [[0 for j in range(W)] for i in range(H)]
#for xy in ab:
#    field[xy[0] - 1][xy[1] - 1] = 1
#print(*field, sep='\n')

count_square = []

def count(h, w):
    #print(h, w)
    for kh in range(-2, 1):
        for kw in range(-2, 1):
            if h + kh >= 0 and w + kw >= 0 and\
                h + kh < H - 2 and w + kw < W - 2:
                #print(h + kh, w + kw)
                count_square.append([h + kh, w + kw])
    #print()

for hw in ab:
    count(hw[0] - 1, hw[1] - 1)

#print(*count_square, sep='\n')
#print()
#count_square.sort()
#print(*count_square, sep='\n')
#print(len(count_square))

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

n = len(count_square)
points = []
while n:
    points.clear()
    points.append(0)
    search = count_square[0]
    COUNT = 1
    for i in range(1, n):
        if search == count_square[i]:
            points.append(i)
            COUNT += 1
    count_list[COUNT] += 1
    for point in reversed(points):
        count_square.pop(point)

    n = len(count_square)

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

print(*count_list, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
H, W, N = list(map(int, input().split(' ')))
ab = [list(map(int, input().split(' '))) for i in range(N)]
#print(ab)

#field = [[0 for j in range(W)] for i in range(H)]
#for xy in ab:
#    field[xy[0] - 1][xy[1] - 1] = 1
#print(*field, sep='\n')

count_square = []

def count(h, w):
    #print(h, w)
    for kh in range(-2, 1):
        for kw in range(-2, 1):
            if h + kh >= 0 and w + kw >= 0 and\
                h + kh < H - 2 and w + kw < W - 2:
                #print(h + kh, w + kw)
                count_square.append([h + kh, w + kw])
    #print()

for hw in ab:
    count(hw[0] - 1, hw[1] - 1)

#print(*count_square, sep='\n')
#print()
count_square.sort()
#print(*count_square, sep='\n')
#print(len(count_square))

count_list = [0 for i in range(10)]
n = len(count_square)
if n == 0:
    count = 0
else:
    count = 1
    for i in range(1, n):
        if count_square[i - 1] == count_square[i]:
            count += 1
        else:
            count_list[count] += 1
            count = 1
    count_list[count] += 1
count_list[0] = (H - 2) * (W - 2) - sum(count_list)

print(*count_list, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
H, W, N = list(map(int, input().split(' ')))
ab = [list(map(int, input().split(' '))) for i in range(N)]
#print(ab)

#field = [[0 for j in range(W)] for i in range(H)]
#for xy in ab:
#    field[xy[0] - 1][xy[1] - 1] = 1
#print(*field, sep='\n')

count_square = [[0 for j in range(W - 2)] for i in range(H - 2)]

def count(h, w):
    #print(h, w)
    for kh in range(-2, 1):
        for kw in range(-2, 1):
            if h + kh >= 0 and w + kw >= 0 and\
                h + kh < H - 2 and w + kw < W - 2:
                #print(h + kh, w + kw)
                count_square[h + kh][w + kw] += 1
    #print()

for hw in ab:
    count(hw[0] - 1, hw[1] - 1)

#print(*count_square, sep='\n')

count_list = [0 for i in range(10)]
for i in range(H - 2):
    for j in range(W - 2):
        count_list[count_square[i][j]] += 1

print(*count_list, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

h, w, n = map(int, input().split())
a_list = [0 for _ in range((w - 2) * (h - 2))]
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 2, a + 1):
        for b_i in range(b - 2, b + 1):
            if (0 <= a_i < h - 2) & (0 <= b_i < w - 2):
                a_list[(b_i * (h - 2)) + a_i] += 1

k = Counter(a_list)
for i in range(10):
    if i in k.keys():
        print(k[i])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

h, w, n = map(int, input().split())
a_list = [[0 for _ in range(w)] for _ in range(h)]
triangle = []
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 1, a + 2):
        for b_i in range(b - 1, b + 2):
            if (1 <= a_i < h - 1) & (1 <= b_i < w - 1):
                triangle.append(str(a_i) + "_" + str(b_i))
aaa = Counter(triangle).values()
dp = [0 for _ in range(10)]
total = 0
for i in aaa:
    dp[i] += 1
    total += 1
dp[0] = ((h - 2) * (w - 2)) - total
for i in dp:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

h, w, n = map(int, input().split())
a_list = [[0 for _ in range(w)] for _ in range(h)]
triangle = []
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 1, a + 2):
        for b_i in range(b - 1, b + 2):
            if (1 <= a_i < h - 1) & (1 <= b_i < w - 1):
                triangle.append(str(a_i) + "_" + str(b_i))
aaa = Counter(list(Counter(triangle).values()))
for i in range(10):
    if i == 0:
        print((h - 2) * (w - 2) -  sum(aaa.values()))
    elif i in aaa.keys():
        print(aaa[i])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import time
input = sys.stdin.readline

H,W,N=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(N)]
ab.sort()

r_b=[0]

r_b_app=r_b.append
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b_app(i)

if N>0:
  r_b_app(N)
rows=tuple(ab[b][0] for b in r_b if b<N)

cols=tuple(tuple(ab[j][1] for j in range(r_b[i],r_b[i+1])) for i in range(len(r_b)-1))

rN=len(cols)


ched_box0=[np.zeros((3,3),dtype=bool) for _ in range((len(cols[0]) if 0<rN else 0))]
ched_box1=[np.zeros((3,3),dtype=bool) for _ in range((len(cols[1]) if 1<rN else 0))]
ched_box2=[np.zeros((3,3),dtype=bool) for _ in range((len(cols[2]) if 2<rN else 0))]

dic_cn0=dict(zip(cols[0],list(range(len(cols[0]))))) if 0<rN else {}
dic_cn1=dict(zip(cols[1],list(range(len(cols[1]))))) if 1<rN else {}
dic_cn2=dict(zip(cols[2],list(range(len(cols[2]))))) if 2<rN else {}

area_n=[0]*9

count=[[1]*3 for i in range(3)]
find_cn=[0]*12

for rn in range(rN):
  cN=len(cols[rn])
  row=rows[rn]

  if rn!=0:
    ched_box0=ched_box1
    dic_cn0=dic_cn1
    ched_box1=ched_box2
    dic_cn1=dic_cn2
    if rn<rN-2:
      cN2_range=range(len(cols[rn+2]))
      ched_box2=np.zeros((len(cols[rn+2]),3,3),dtype=bool)
      dic_cn2=dict(zip(cols[rn+2],list(cN2_range)))

  if (rows[rn+1]==row+1 if rn<rN-1 else False):
    row1=row+1
    if (rows[rn+2]==row+2 if rn<rN-2 else False):
      row2=row+2
    else:
      row2=None
  elif (rows[rn+1]==row+2 if rn<rN-1 else False):
    row1=row+2
    row2=None
  else:
    row1=None
    row2=None
  find_rowcol=np.zeros((5,5),dtype=int)
  for cn in range(cN):
    col=cols[rn][cn]
    ched_box=ched_box0[cn]

    
    for box_row,box_col in zip(*np.where(ched_box==False)):
      if col-2+box_col<1 or col+box_col>W or row-2+box_row<1 or row+box_row>H:
        ched_box[box_row][box_col]=True    

    for ch_row in range(5):
      for ch_col in range(5):
        find_rowcol[ch_row,ch_col]=0
        
    find_cn=[[0]*5 for _ in range(3)]

    find_rowcol[2,2]=1
    find_cn[0][2]=cn
    if (col+1 in dic_cn0 if col+1<=W else False):
      find_rowcol[2,3]=1
      find_cn[0][3]=dic_cn0[col+1]
    if (col+2 in dic_cn0 if col+2<=W else False):
      find_rowcol[2,4]=1
      find_cn[0][4]=dic_cn0[col+2]
    if (row1<=H if row1 is not None else False):
      for ch_col in range(max(col-2,1),min(col+3,W+1)):
        if ch_col in dic_cn1:
          find_rowcol[row1-row+2,ch_col-col+2]=1
          find_cn[row1-row][ch_col-col+2]=dic_cn1[ch_col]
    if (row2<=H if row2 is not None else False):
      for ch_col in range(max(col-2,1),min(col+3,W+1)):
        if ch_col in dic_cn2:
          find_rowcol[row2-row+2,ch_col-col+2]=1
          find_cn[row2-row][ch_col-col+2]=dic_cn2[ch_col]

             
   
    for box_row,box_col in zip(*np.where(ched_box==False)):
      area_n[find_rowcol[box_row:box_row+3,box_col:box_col+3].sum()-1]+=1
    for ch_row,ch_col in zip(*np.where(find_rowcol)):
      for box_row in range(5-ch_row):
        for box_col in range((0 if ch_col>=2 else 2-ch_col),(5-ch_col if ch_col>=2 else 3)):
          if ch_row==2:
            ched_box0[find_cn[ch_row-2][ch_col]][box_row][box_col]=True
          elif ch_row==row1-row+2:
            ched_box1[find_cn[ch_row-2][ch_col]][box_row][box_col]=True
          elif ch_row==row2-row+2:
            ched_box2[find_cn[ch_row-2][ch_col]][box_row][box_col]=True




print((W-2)*(H-2)-sum(area_n))
for i in range(9):
  print(area_n[i])