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

#塗りつぶす座標の集合ｓ
s = []
for i in range(n):
    arr = list(map(int,input().split()))
    s.append(arr)

#0~9 順に四角形内の塗りつぶされている座標の数を調べる
for i in range(10):
    #bはiと四角形内の塗りつぶされている座標の数が一致する四角形の数
    b=0
    for j in range(h-2):
        for k in range(w-2):
            #aは四角形内の塗りつぶされている座標の数
            a=0
            area=[]
            for x in range(1,4):
                area.append([j+x,k+1])
                area.append([j+x,k+2])
                area.append([j+x,k+3])
            #print(area)
            for l in s:
                if l in area:
                    a += 1
            if a == i:
                b += 1
        
    print(b)

Submission status: Time Limit Exceeded

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

#塗りつぶす座標の集合ｓ
s = []
for i in range(n):
    arr = list(map(int,input().split()))
    s.append(arr)

#0~9 順に四角形内の塗りつぶされている座標の数を調べる
for i in range(10):
    #bはiと四角形内の塗りつぶされている座標の数が一致する四角形の数
    b=0
    for j in range(h-2):
        for k in range(w-2):
            #aは四角形内の塗りつぶされている座標の数
            a=0
            area=[]
            for x in range(1,4):
                for y in range(1,4):
                    area.append([j+x,k+y])
            #print(area)
            for l in s:
                if l in area:
                    a += 1
            if a == i:
                b += 1
        
    print(b)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,n=map(int,input().split())
ans=[0]*10
p=set()
q=set()
for i in range(n):
	a,b=map(int,input().split())
	for j in range(-1,2):
		for k in range(-1,2):
			if 2<=a+j<=h-1 and 2<=b+k<=w-1:
				r=(a+j)*(10**10)+b+k
				p.add(r)
	q.add(a*(10**10)+b)
p=list(p)
for x in p:
	cnt=0
	for j in range(-1,2):
		for k in range(-1,2):
			if x+j*(10**10)+k in q:
				cnt+=1
	ans[cnt]+=1
print((h-2)*(w-2)-sum(ans[1:]))
for i in range(1,10):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
input = sys.stdin.readline

def main():
    h, w, n = map(int, input().split())
    grid = [0]*n
    mod = 10**9
    for i in range(n):
        a, b = map(int, input().split())
        grid[i] = a*mod+b
    
    ans = [0]*10
    already = dict()
    key = 0
    for value in combinations(grid, r=1):
        a, b = divmod(value[0], mod)
        for i in range(-1, 2):
            for j in range(-1, 2):
                if  a+i <= 1 or a+i >= h or b+j <= 1 or b+j >= w:
                    continue
                if (a+i, b+j) in already:
                    continue
                already[(a+i, b+j)] = 1
                key += 1
                count = 0
                for p in range(-1, 2):
                    for q in range(-1, 2):
                        if (a+i+p)*mod+b+j+q in grid:
                            count += 1
                ans[count] += 1
    
    for i in range(10):
        if i == 0:
            print((h-2)*(w-2)-key+ans[0])
            continue
        print(ans[i])

    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
h,w,n=map(int,input().split())
ans=[0]*10
a=[]
for i in range(n):
  a+=[list(map(int,input().split()))]
a=sorted(a)
for x,y in a:
  b=[[x-2,y-2],[x-1,y-2],[x,y-2],[x-2,y-1],[x-1,y-1],[x,y-1],[x-2,y],[x-1,y],[x,y]]
  for l,m in b:
    cnt=0
    if not(0<l<=h-2 and 0<m<=w-2):continue
    for i in range(3):
      for j in range(3):
        ni=l+i
        nj=m+j
        k=bisect.bisect_left(a,[ni,nj])
        if k<n and a[k]==[ni,nj]:
          cnt+=1
    ans[cnt]+=1
for i in range(1,10):
  ans[i]//=i
ans[0]=(h-2)*(w-2)-sum(ans)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
h,w,n = map(int,input().split())
s = [[0 for j in range(w+2)] for i in range(h+2)]
#print(s)
for i in range(0,n):
    x,y = map(int,input().split())
    s[x-1][y-1] += 1
    s[x-1][y] += 1
    s[x-1][y+1] += 1
    s[x][y-1] += 1
    s[x][y] += 1
    s[x][y+1] += 1
    s[x+1][y-1] += 1
    s[x+1][y] += 1
    s[x+1][y+1] += 1

#print(s)
ans = [0] * 10
for i in range(2,h):
    for j in range(2,w):
        ans[s[i][j]] += 1
for i in range(0,10):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W, N = getNM()
query = [getList() for i in range(N)]
list_star = defaultdict(set)
H_max = 0
W_max = 0
for y, x in query:
    H_max = max(H_max, y)
    W_max = max(W_max, x)
    list_star[y - 1].add(x - 1)

dx = [0, 0, 1, 1, 1, 0, -1, -1, -1]
dy = [0, 1, 1, 0, -1, -1, -1, 0, 1]


lista = [0] * 10

def counter(x, y):
    if x <= 0 or W - 1 <= x or y <= 0 or H - 1 <= y:
        return 0
    cnt = 0
    for i in range(9):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < W and 0 <= ny < H:
            if nx in list_star[ny]:
                cnt += 1
    return cnt

star_list = set()
for y, x in query:
    x -= 1
    y -= 1
    for l in range(9):
        nx = x + dx[l]
        ny = y + dy[l]
        if (nx, ny) in star_list:
            continue
        opt = counter(nx, ny)
        if opt:
            lista[opt] += 1
            star_list.add((nx, ny))

left = (H - 2) * (W - 2) - sum(lista)
lista[0] = left
for i in lista:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def read_int():
    return int(input().strip())


def read_ints():
    return tuple(map(int, input().strip().split(' ')))


def read_coords():
    return tuple(int(i)-1 for i in input().strip().split(' '))


def solve():
    """

   ...
   .B.
   ...
    """
    H, W, N = read_ints()
    black_cells = set()
    cell_counter = {} # (x, y) -> count
    for _ in range(N):
        black_cells.add(read_coords())
    for a, b in black_cells:
        for i in range(-1, 2):
            for j in range(-1, 2):
                if 1 <= a+i < H-1 and 1 <= b+j < W-1:
                    cell_counter[(a+i, b+j)] = sum(
                        1 if (x, y) in black_cells else 0
                        for x in range(a+i-1, a+i+2)
                        for y in range(b+j-1, b+j+2))
    total = (H-2)*(W-2)
    count = {i: 0 for i in range(1, 10)}
    C = 0
    for k, v in cell_counter.items():
        count[v] += 1
        C += 1
    count[0] = total-C
    for i in range(10):
        print(count[i])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return tuple(map(int, input().strip().split(' ')))


def read_coords():
    return tuple(int(i)-1 for i in input().strip().split(' '))


def solve():
    """

   ...
   .B.
   ...
    """
    H, W, N = read_ints()
    black_cells = set()
    cell_counter = {} # (x, y) -> count
    for _ in range(N):
        black_cells.add(read_coords())
    for a, b in black_cells:
        for i in range(-1, 2):
            for j in range(-1, 2):
                if 1 <= a+i < H-1 and 1 <= b+j < W-1:
                    cell_counter[(a+i, b+j)] = sum(
                        1 if (x, y) in black_cells else 0
                        for x in range(a+i-1, a+i+2)
                        for y in range(b+j-1, b+j+2))
    total = (H-2)*(W-2)
    count = {i: 0 for i in range(1, 10)}
    C = 0
    for k, v in cell_counter.items():
        count[v] += 1
        C += 1
    count[0] = total-C
    for i in range(10):
        print(count[i])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W,N = map(int,input().split())
    point = [tuple(map(int,input().split())) for _ in range(N)]
    searched = set()

    ans = [0] * 10
    tot = 0
    for p,q in point:
        neighbor = [[0]*5 for _ in range(5)]
        for dy in (-2,-1,0,1,2):
            for dx in (-2,-1,0,1,2):
                if (p + dy,q + dx) in point:
                    neighbor[dy + 2][dx + 2] = 1
        
        for i in range(1,4):
            for j in range(1,4):
                if p + i - 2 <= 1 or p + i - 2 >= H:
                    continue
                if q + j - 2 <= 1 or q + j - 2 >= W:
                    continue
                if (p + i - 2,q + j - 2) in searched:
                    continue
                searched.add((p + i - 2,q + j - 2))
                cnt = 0
                for dy in (-1,0,1):
                    for dx in (-1,0,1):
                        if neighbor[i + dy][j + dx]:
                            cnt += 1
                tot += 1
                ans[cnt] += 1
    ans[0] = (H - 2)*(W - 2) - tot
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def f(r,c,i,j,P,H,W):
    n = 0
    if r-i<0 or r-i+2>=H:return 0
    if c-j<0 or c-j+2>=W:return 0
    for pr,pc in P:
        if r-i<=pr<=r-i+2 and c-j<=pc<=c-j+2:n+=1
    return n
def count(res, r, c, P,H,W):
    for i in range(3):
        for j in range(3):
            n=f(r,c,i,j,P,H,W)
            if n>0:res[n]+=1
def main():
    H,W,N=tuple(map(int,sys.stdin.readline().split()))
    res=[0]*10
    res[0]=(H-2)*(W-2)
    if N!=0:
        P=[tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for _ in [0]*N]
        P.sort()
        for r,c in P:count(res,r,c,P,H,W)
        for i in range(1,10):res[i]//=i
        res[0]-=sum(res[1:])
    for r in res:
        print(r)
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
x, y, n = map(int, input().split())
box = [[0 for _ in range(y)] for _ in range(x)]
for _ in range(n):
    a, b = map(int, input().split())
    box[a - 1][b - 1] = 1
table = [0] * 10
for i in range(x - 2):
    for j in range(y - 2):
        total = sum(box[i][j:j + 3]) + sum(box[i + 1][j:j + 3]) + sum(box[i + 2][j:j + 3])
        table[total] += 1

[print(a) for a in table]

Submission status: Time Limit Exceeded

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

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

for i in range(n):
  x,y = input().split()
  x,y = int(x)-1, int(y)-1
  masu[x][y] = 1
  
count = [0] * 10

for i in range(h-2):
  for j in range(w-2):
    shiro = 0
    for _x in range(3):
      for _y in range(3):
        if masu[i+_x][j+_y] == 1:
          shiro += 1
    count[shiro] += 1
print(*count, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

def input():
    return sys.stdin.readline().strip()

def recordnum(a,b):
    if not (0 < a < H-1 and 0 < b < W-1):
        return 

    res = M[(a,b)]
    for i,j in vector:
        res += M[(a+i,b+j)]
    num[res] += 1
    return

def dfs(a,b,color):

    if visited[(a,b)]:
        return

    recordnum(a,b)
    visited[(a,b)] = True

    if color == "b":
        for i,j in vector:
            x = a+i
            y = b+j
            if 0 < x < H-1 and 0 < y < W-1 and M[(x,y)] == 0:
                dfs(x,y,"w")
    return

    

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

M = defaultdict(int)
visited = defaultdict(int)
ab = []

for _ in range(N):
    a,b = map(int,input().split())
    ab.append((a-1,b-1))
    M[(a-1,b-1)] = 1


vector = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]
num = [0]*10

for a,b in ab:
    dfs(a,b,"b")

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

for i in num:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

def input():
    return sys.stdin.readline().strip()

def recordnum(a,b):
    if not (0 < a < H-1 and 0 < b < W-1):
        return 
    else:
        res = M[(a,b)]
        for i,j in vector:
            res += M[(a+i,b+j)]
        num[res] += 1
        return


def dfs(a,b,color):

    if visited[(a,b)]:
        return
    
    recordnum(a,b)
    visited[(a,b)] = True

    if color == "b":
        for i,j in vector:
            x = a+i
            y = b+j
            if 0 < x < H-1 and 0 < y < W-1 and not M[(x,y)]:
                dfs(x,y,"w")
    return

    

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

M = defaultdict(int)
visited = defaultdict(int)
ab = []

for _ in range(N):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
    M[(a-1,b-1)] = 1


vector = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]
num = [0]*10

for a,b in ab:
    dfs(a,b,"b")

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

for i in num:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

H, W, N = map(int, input().split())
V = set([tuple(map(int, input().split())) for _ in range(N)])
D = tuple(product((-1, 0, 1), repeat=2))

A = set()
for a, b in V:
    for h, w in D:
        if 2 <= a + h <= H - 1 and 2 <= b + w <= W - 1:
            A.add((a + h, b + w))

ans = [0] * 10
for a, b in A:
    cnt = 0
    for h, w in D:
        if (a + h, b + w) in V:
            cnt += 1
    ans[cnt] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

int1 = lambda x: int(x) - 1

H, W, N = map(int, input().split())
B = set(tuple(map(int1, input().split())) for _ in range(N))

adj = (-1, 0, 1)
visited = set()
ans = [0] * 10
for a, b in B:
    for dy, dx in itertools.product(adj, repeat=2):
        if not (1 <= a + dy < H - 1 and 1 <= b + dx < W - 1):
            continue
        elif (a + dy, b + dx) in visited:
            continue
        visited.add((a + dy, b + dx))
        c = 0
        for ddy, ddx in itertools.product(adj, repeat=2):
            if (a + dy + ddy, b + dx + ddx) in B:
                c += 1
        ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
H,W,N=map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
tpl = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]
edge_WtoB = dd(list)
edge_BtoB = dd(list)
node_B = set(ab)
node_W = set()
res = dd(int)
# 今見てるマスが黒
for a,b in ab:
    for s,t in tpl:
        tgt = (a+s,b+t)
        # 隣接マスも黒
        if tgt in node_B:
            if not (1 < a < H and 1 < b < W):
                continue
            edge_BtoB[(a,b)].append(tgt)
        # 隣接マスは白
        else:
            if not (1 < a + s < H and 1 < b + t < W):
                continue
            edge_WtoB[tgt].append((a,b))
            node_W.add(tgt)
for tgt in node_W:
    res[len(edge_WtoB[tgt])] += 1
for tgt in node_B:
    res[len(edge_BtoB[tgt])] += 1
zero = (H-2)*(W-2)
for j in range(1,10):
    zero -= res[j]
res[0] = zero
for j in range(10):
    print(res[j])

Submission status: Time Limit Exceeded

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

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

dxy = {0:[0, 1, 2], 1:[-1, 0, 1], 2:[-2, -1, 0]}
num_all = (H - 2) * (W - 2)
num = [0] * 10
for a, b in ab:
  for i in range(3):
    Da = dxy[i]
    for j in range(3):
      n = 0
      flag = False
      Db = dxy[j]
      for da in Da:
        aa = a + da
        for db in Db:
          bb = b + db
          if aa < 1 or H < aa or bb < 1 or W < bb:
            flag = True
            break
          if (aa, bb) in ab:
            n += 1
        if flag:
          break
      if flag:
        continue
      num[n] += 1

for i in range(2, 10):
  num[i] //= i

num[0] = num_all - sum(num[1:])
print(*num, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    class TwoDimNode:
        def __init__(self, x=None, y=None, parent=None, left=None, right=None):
            """
            2 次元二分探索木のためのノード
            """        
            self.x = x
            self.y = y
            self.parent = parent
            self.left = left
            self.right = right
            self.flag = True

    class TwoDimTree:
        def __init__(self, points=[]):
            """
            2 次元二分探索木 (kD tree) を作成する
            root の深さを 0 として、深さが偶数の場合そこでは x を基準に、奇数の場合 y を基準に二分探索木条件を満たすようにする
            """
            # nil の設定
            self.nil = TwoDimNode()
            self.nil.parent = self.nil
            self.nil.left = self.nil
            self.nil.right = self.nil
            # root の設定
            self.root = self.nil
            # もし予め一次元の点の集合が与えられるのならバランスする形で kD tree を構築する
            self._balance_insert(points)


        def _balance_insert(self, seq, depth=0):
            # 毎回 x or y をキーとしてソートを行い、中央値をとって insert すれば平衡になる
            if seq:
                arranged = sorted(seq, key=itemgetter(depth % 2))
                mid = len(seq) // 2
                self.insert(seq[mid][0], seq[mid][1])
                self._balance_insert(arranged[:mid], depth+1)
                self._balance_insert(arranged[mid+1:], depth+1)


        def insert(self, x, y):
            """
            kD tree に値が (x, y) であるノードを O(depth) で挿入する
            (コンストラクタで生成した kD tree は平衡であることが保証されるが、insert により生成した部分の平衡性は保証されないことに注意)        
            """
            trailer = self.nil    # (x, y) を挿入するべき nil の一つ前のノードを保存するトレーラポインタ
            pos = self.root    # (x, y) を挿入するべき nil の場所を探す
            depth = 0
            while pos != self.nil:
                trailer = pos
                k, pos_k = (x, pos.x) if depth % 2 == 0 else (y, pos.y)
                if k < pos_k:
                    pos = pos.left
                elif pos_k < k:
                    pos = pos.right
                else:
                    pos.flag ^= pos.flag
                    pos = pos.left if pos.flag else pos.right
                depth += 1
            inserted_node = TwoDimNode(x, y, trailer, self.nil, self.nil)
            # trailer の depth
            depth -= 1
            k, trailer_k = (x, trailer.x) if depth % 2 == 0 else (y, trailer.y)
            # tree is empty
            if trailer == self.nil:
                self.root = inserted_node
            # どこかのノードの子供の位置に挿入する時
            elif k < trailer_k or (k == trailer_k and trailer.flag):
                trailer.left = inserted_node
            else:
                trailer.right = inserted_node
        
        def two_dim_search(self, sx, tx, sy, ty, node=None, depth=0):
            """
            kD tree に対し閉区間 D = {(x, y) | sx<=x<=tx, sy<=y<=ty} 内に存在する点を探してリストにまとめて返す (対応する点の個数 k として O(√n + k))
            下記のように検索必要性を判断し再帰的に左右の子に対し探索を行えば良い

            <-------- node.x -------->
            <----------->
            少しでも [sx,tx] が左側ゾーン ((-inf, node.x]) に被っていたら検索しておく必要がある
                        <----->
                        少しでも [sx, tx] が右側ゾーン ([node.x, inf)) に被っていたら検索しておく必要がある
            """        
            cnt = 0
            node = self.root if node is None else node
            # print(f"{node.x} {node.y}")
            if depth % 2 == 0:
                if node.left != self.nil and sx <= node.x:
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    cnt += 1
                if node.right != self.nil and tx >= node.x:
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
            else:
                if node.left != self.nil and sy <= node.y:
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    cnt += 1
                if node.right != self.nil and ty >= node.y:
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
            return cnt


    def unvisited_p(d, i, j):
        if i in d:
            if j in d[i]:
                return False
        return True

    def register(d, i, j):
        if i not in d:
            d[i] = set()
            d[i].add(j)
        else:
            d[i].add(j)

    
    h, w, n = mi()
    points = [lmi() for _ in range(n)]

    num_of_grids_contains_black = [0] * 10

    # kD tree 処理
    kd_tree = TwoDimTree()
    for x, y in points:
        kd_tree.insert(x, y)

    d = dict()
    for x, y in points:
        # print(f"{x} {y} {kd_tree.two_dim_search(x-1, x+1, y-1, y+1)}")
        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if 2 <= i <= h-1 and 2 <= j <= w-1 and unvisited_p(d, i, j):    # 探索する 3*3 grid のセンター
                    num_of_grids_contains_black[kd_tree.two_dim_search(i-1, i+1, j-1, j+1)] += 1
                    register(d, i, j)


    num_of_grids_contains_black[0] = (h - 2) * (w - 2) - sum(num_of_grids_contains_black[1:])
    print(*num_of_grids_contains_black, sep='\n')



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def contained_in_dict_set(d, i, j):
        if i in d:
            if j in d[i]:
                return True
        return False
    
    def register_dict_set(d, i, j):
        if i not in d:
            d[i] = set()
        d[i].add(j)

    def count_black_around_center(point_dict, i, j):
        cnt = 0
        for s in range(i-1, i+2):
            for t in range(j-1, j+2):
                if contained_in_dict_set(point_dict, s, t):
                    cnt += 1
        return cnt
    

    h, w, n = mi()
    points = [lmi() for _ in range(n)]
    num_of_grids_contains_black = [0] * 10

    point_dict = dict()
    visited_dict = dict()

    for x, y in points:
        register_dict_set(point_dict, x, y)

    for x, y in points:
        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if 2<=i<=h-1 and 2<=j<=w-1 and not contained_in_dict_set(visited_dict, i, j):
                    cnt = count_black_around_center(point_dict, i, j)
                    num_of_grids_contains_black[cnt] += 1
                    register_dict_set(visited_dict, i, j)
    
    num_of_grids_contains_black[0] = (h - 2) * (w - 2) - sum(num_of_grids_contains_black[1:])
    print(*num_of_grids_contains_black, sep='\n')    



if __name__ == "__main__":
    main()