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:
#!/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)
from random import shuffle

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):
            self.x = x
            self.y = y
            self.parent = parent
            self.left = left
            self.right = right
            self.flag = True

    class TwoDimTree:
        def __init__(self):
            self.nil = TwoDimNode()
            self.nil.parent = self.nil
            self.nil.left = self.nil
            self.nil.right = self.nil
            self.root = self.nil
                
        def insert(self, x, y):
            trailer = self.nil
            pos = self.root
            depth = 0
            while pos != self.nil:
                trailer = pos
                if depth % 2 == 0:
                    k, pos_k = x, pos.x
                else:
                    k, pos_k = 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
            if depth % 2 == 0:
                k, trailer_k = x, trailer.x
            else:
                k, trailer_k = 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):
            # buf = []
            cnt = 0
            if node is None:
                node = self.root
            # print(f"{node.x} {node.y}")
            if depth % 2 == 0:
                if node.left != self.nil and sx <= node.x:
                    # buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    # buf.append((node.x, node.y))
                    cnt += 1
                if node.right != self.nil and tx >= node.x:
                    # buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
            else:
                if node.left != self.nil and sy <= node.y:
                    # buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                    cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    # buf.append((node.x, node.y))
                    cnt += 1
                if node.right != self.nil and ty >= node.y:
                    # buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
                    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)]
    shuffle(points)

    num_of_grids_contains_black = [0] * 10

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



    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 のセンター
                    # print(f"{i} {j}")
                    # print(kd_tree.two_dim_search(i-1, i+1, j-1, j+1))
                    # num_of_grids_contains_black[len(kd_tree.two_dim_search(i-1, i+1, j-1, j+1))] += 1
                    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)
from random import shuffle

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):
            self.x = x
            self.y = y
            self.parent = parent
            self.left = left
            self.right = right
            self.flag = True

    class TwoDimTree:
        def __init__(self):
            self.nil = TwoDimNode()
            self.nil.parent = self.nil
            self.nil.left = self.nil
            self.nil.right = self.nil
            self.root = self.nil
        

                
        def insert(self, x, y):
            trailer = self.nil
            pos = self.root
            depth = 0
            while pos != self.nil:
                trailer = pos
                if depth % 2 == 0:
                    k, pos_k = x, pos.x
                else:
                    k, pos_k = 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
            if depth % 2 == 0:
                k, trailer_k = x, trailer.x
            else:
                k, trailer_k = 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):
            buf = []
            if node is None:
                node = self.root
            # print(f"{node.x} {node.y}")
            if depth % 2 == 0:
                if node.left != self.nil and sx <= node.x:
                    buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    buf.append((node.x, node.y))
                if node.right != self.nil and tx >= node.x:
                    buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
            else:
                if node.left != self.nil and sy <= node.y:
                    buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
                if sx <= node.x <= tx and sy <= node.y <= ty:
                    buf.append((node.x, node.y))
                if node.right != self.nil and ty >= node.y:
                    buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
            return buf

    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)]
    shuffle(points)

    num_of_grids_contains_black = [0] * 10

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



    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 のセンター
                    # print(f"{i} {j}")
                    # print(kd_tree.two_dim_search(i-1, i+1, j-1, j+1))
                    num_of_grids_contains_black[len(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:
H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
from bisect import bisect_left
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx) + str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    if x > 9:
        while True:
            print(W)
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import *
h, w, n = map(int, input().split())

d = defaultdict(list)
q = [list(map(int, input().split())) for i in range(n)]
q.sort()
ans = [0]*10
for i in range(n):
    a, b = q[i]
    d[a].append(b)

for a, b in q:
    for i in range(max(1, a-2), min(h-2, a)+1):
        for j in range(max(1, b-2), min(w-2, b)+1):
            count = 0
            for k in range(3):
                count += bisect_right(d[i+k], j+2) - bisect_left(d[i+k], j)
            ans[count] += 1


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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


h,w,n = list(map(int, input().split()))
painted = []
for i in range(n):
    t = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            painted.append([t[0]-2+j, t[1]-2+k])
    
painted.sort(key = lambda x : x[1])
painted.sort(key = lambda x : x[0])

p2 = []

for i in painted:
    if(i[0]>=1 and i[0]<h-1 and i[1]>=1 and i[1]<w-1):
        p2.append(i)

#print(p2)
ans = [0 for i in range(10)]
chain=0
if(len(p2)>0):
    before = p2[0]
    chain = 1
for ii in range(len(p2)-1):
    i = ii+1
    if(p2[i][0] == before[0] and p2[i][1] == before[1]):
        chain += 1
    else:
        ans[chain]+=1
        chain=1
        before[0],before[1] = p2[i]
if(len(p2)>0): ans[chain]+=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W, N = map(int, input().split())
cand = set()
dot = set()
for _ in range(N):
    x, y = map(int, input().split())
    dot.add((x, y))
    for i in range(-2, 1):
        if 1 <= x + i <= H - 2:
            for j in range(-2, 1):
                if 1 <= y + j <= W - 2:
                    cand.add((x + i, y + j))

ans = [0] * 10
for x, y in cand:
    cnt = 0
    for i in range(3):
        for j in range(3):
            cnt += int((x + i, y + j) in dot)
    ans[cnt] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W, N = map(int, input().split())
xy = []
dot = defaultdict(int)
seen = defaultdict(bool)
for _ in range(N):
    a, b = map(int, input().split())
    xy.append((a, b))
    dot[(a, b)] = 1

ans = [0] * 10
for x, y in xy:
    for dx in [-2, -1, 0]:
        for dy in [-2, -1, 0]:
            nx = x + dx
            ny = y + dy
            if seen[(nx, ny)] or nx <= 0 or nx + 2 > H or ny <= 0 or ny + 2 > W:
                continue
            seen[(nx, ny)] = True
            cnt = 0
            for i in range(3):
                for j in range(3):
                    cnt += int(dot[(nx + i, ny + j)])
            ans[cnt] += 1

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

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int,input().split())
ans = [0 for _ in range(10)]
points = []
MAP = [[0 for i in range(W)] for j in range(H)]
for _ in range(N):
    a, b = map(int,input().split())
    MAP[a-1][b-1] = 1
    points.append([a-1, b-1])
for i in range(N):
    a, b = points[i]
    for p in range(-1, 2):
        for q in range(-1, 2):
            cnt = 0
            if 1 <= a + p <= H - 2 and 1 <= b + q <= W - 2:
                for h in range(-1, 2):
                    cnt += sum(MAP[a + p + h][b + q - 1: b + q + 2])
            ans[cnt] += 1
for i in range(1,10):
    ans[i] //= i
SUM = sum(ans[1:])
ans[0] = (H-2) * (W-2) - SUM
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
H,W,N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp=[[0 for i in range(W-2)] for j in range(H-2)]
for i in range(0,N):
    h = ab[i][0]
    w = ab[i][1]
    for j in range(max(0,h-3),min(h,H-2)):
        for k in range(max(0,w-3),min(w,W-2)):
            dp[j][k] = dp[j][k]+1

import itertools

res = list(itertools.chain.from_iterable(dp))

for i in range(0,10):
    print(res.count(i))

Submission status: Time Limit Exceeded

Solution code:
H, W, N = input().split(" ")
H, W, N = int(H), int(W), int(N)
A = [input().split(" ") for i in range(N)]
A = [[int(l[0])-1, int(l[1])-1] for l in A]

sq3_3 = [[0 for w in range(W - 3 + 1)] for h in range(H - 3 + 1)]

for p, q in A:
    for k in [0, 1, 2]:
        for l in [0, 1, 2]:
            if 0 <= p-k < H-3+1 and 0 <= q-l < W-3+1:
                sq3_3[p - k][q - l] += 1

l = []
for s in sq3_3:
    l += s

for i in range(10):
    print(l.count(i))

Submission status: Time Limit Exceeded

Solution code:
H, W, N = input().split(" ")
H, W, N = int(H), int(W), int(N)
A = [input().split(" ") for i in range(N)]
A = [[int(l[0])-1, int(l[1])-1] for l in A]

sq3_3 = [[0 for w in range(W - 3 + 1)] for h in range(H - 3 + 1)]
sq3_3

for p, q in A:
    for k in [0, 1, 2]:
        for l in [0, 1, 2]:
            if 0 <= p-k < H-3+1 and 0 <= q-l < W-3+1:
                sq3_3[p - k][q - l] += 1
sq3_3

l = []
for s in sq3_3:
    l += s

for i in range(10):
    print(l.count(i))

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
li = []
for i in range(N):
  li.append(tuple(map(int, input().split())))
t = tuple(li)
#print(t)

Js = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

for a, b in t:
  if a > H-2 or b > W-2:
    pass
  else:
    t_p1 = ((a, b), (a, b+1), (a, b+2),\
            (a+1, b), (a+1, b+1), (a+1, b+2),\
            (a+2, b), (a+2, b+1), (a+2, b+2))
    s1 = set(t) & set(t_p1)
    ls1 = len(s1)
    Js[ls1] += 1
  
  if a > H-2 or b > W-1 or b < 2:
    pass
  else:
    t_p2 = ((a, b-1), (a, b), (a, b+1),\
            (a+1, b-1), (a+1, b), (a+1, b+1),\
            (a+2, b-1), (a+2, b), (a+2, b+1))
    s2 = set(t) & set(t_p2)
    ls2 = len(s2)
    Js[ls2] += 1
  
  if a > H-2 or b < 3:
    pass
  else:
    t_p3 = ((a, b-2), (a, b-1), (a, b),\
            (a+1, b-2), (a+1, b-1), (a+1, b),\
            (a+2, b-2), (a+2, b-1), (a+2, b))
    s3 = set(t) & set(t_p3)
    ls3 = len(s3)
    Js[ls3] += 1

  if a > H-1 or a < 2 or b > W-2:
    pass
  else:
    t_p4 = ((a-1, b), (a-1, b+1), (a-1, b+2),\
            (a, b), (a, b+1), (a, b+2),\
            (a+1, b), (a+1, b+1), (a+1, b+2))
    s4 = set(t) & set(t_p4)
    ls4 = len(s4)
    Js[ls4] += 1
  
  if a > H-1 or a < 2 or b > W-1 or b < 2:
    pass
  else:
    t_p5 = ((a-1, b-1), (a-1, b), (a-1, b+1),\
            (a, b-1), (a, b), (a, b+1),\
            (a+1, b-1), (a+1, b), (a+1, b+1))
    s5 = set(t) & set(t_p5)
    ls5 = len(s5)
    Js[ls5] += 1
  
  if a > H-1 or a < 2 or b < 3:
    pass
  else:
    t_p6 = ((a-1, b-2), (a-1, b-1), (a-1, b),\
            (a, b-2), (a, b-1), (a, b),\
            (a+1, b-2), (a+1, b-1), (a+1, b))
    s6 = set(t) & set(t_p6)
    ls6 = len(s6)
    Js[ls6] += 1
  
  if a < 3 or b > W-2:
    pass
  else:
    t_p7 = ((a-2, b), (a-2, b+1), (a-2, b+2),\
            (a-1, b), (a-1, b+1), (a-1, b+2),\
            (a, b), (a, b+1), (a, b+2))
    s7 = set(t) & set(t_p7)
    ls7 = len(s7)
    Js[ls7] += 1
  
  if a < 3 or b > W-1 or b < 2:
    pass
  else:
    t_p8 = ((a-2, b-1), (a-2, b), (a-2, b+1),\
            (a-1, b-1), (a-1, b), (a-1, b+1),\
            (a, b-1), (a, b), (a, b+1))
    s8 = set(t) & set(t_p8)
    ls8 = len(s8)
    Js[ls8] += 1
  
  if a < 3 or b < 3:
    pass
  else:
    t_p9 = ((a-2, b-2), (a-2, b-1), (a-2, b),\
            (a-1, b-2), (a-1, b-1), (a-1, b),\
            (a, b-2), (a, b-1), (a, b))
    s9 = set(t) & set(t_p9)
    ls9 = len(s9)
    Js[ls9] += 1

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

all = (H - 2) * (W - 2)
Js[0] = all - sum(Js)
  
for i in range(10):
  print(Js[i])

Submission status: Time Limit Exceeded

Solution code:
def solve(h,w,n,black_list):
  idx_list = []
  for idx, (a,b) in enumerate(black_list):
    left = max(0, b-3)
    top = max(0, a-3)
    for row in range(top, a):
      if row+2 >= h:
        continue
      for col in range(left, b):
        if col+2 >= w:
          continue
        idx_list.append(row*h+col)

  set_count = set(idx_list)
  ans = [0]*len(set_count)
  for idx,i in enumerate(set_count):
    ans[idx] = idx_list.count(i)

  ret = [(h-2)*(w-2)-len(set_count)]
  for i in range(1, 10):
    ret.append(ans.count(i))
  return ret

if __name__ == "__main__":
  h,w,n = map(int,input().split())
  black_list = [tuple(map(int,input().split())) for _ in range(n)]
  ret = solve(h,w,n,black_list)
  for i in ret:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(h,w,n,black_list):
  count = []
  for idx, (a,b) in enumerate(black_list):
    left = max(0, b-3)
    top = max(0, a-3)
    right = min(w, b+3)
    bottom = min(h, a+3)
    for row in range(top, a):
      if row+2 >= h:
        continue
      for col in range(left, b):
        if col+2 >= w:
          continue
        count.append(row*h+col)

  set_count = set(count)
  count = np.array(count)
  ans = np.zeros(len(set_count))
  for idx,i in enumerate(set_count):
    ans[idx] = np.count_nonzero(count==i)

  ret = [(h-2)*(w-2)-len(set_count)]
  for i in range(1, 10):
    ret.append(np.count_nonzero(ans==i))
  return ret

if __name__ == "__main__":
  h,w,n = map(int,input().split())
  black_list = [tuple(map(int,input().split())) for _ in range(n)]
  ret = solve(h,w,n,black_list)
  for i in ret:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#in1 = '4 5 8'
#in2 = ['1 1', '1 4', '1 5', '2 3', '3 1', '3 2', '3 4', '4 4']
#in1 = '10 10 20'
#in2 = ['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']
#in1 = '1000000000 1000000000 0'
#h, w, n = map(int, in1.split())
h, w, n = map(int, input().split())

"""
10010
00000
00000
00000
"""

idx1 = 0
ab = [[0 for i in range(2)] for j in range(n)]

black_cnt = [0] * 10
black_cnt[0] = (h - 2) * (w - 2)

if n != 0:
    while idx1 < n:
        x = input().split()
        #x = in2[idx1].split()
        ab[idx1] = [int(x[0]), int(x[1])]
        idx1 += 1

    for idx1 in range(len(ab)):
        if ab[idx1][0] < 3:
            sr = 0
        else:
            sr = ab[idx1][0] - 3
        if ab[idx1][0] > h - 2:
            lr = h - 2
        else:
            lr = ab[idx1][0]

        if ab[idx1][1] < 3:
            sc = 0
        else:
            sc = ab[idx1][1] - 3
        if ab[idx1][1] > w - 2:
            lc = w - 2
        else:
            lc = ab[idx1][1]

        #print('s_Row:{} l_Row:{} s_Col:{} l_Col:{}'.format(sr, lr, sc, lc))
        for nowRow in range(sr, lr):
            for nowCol in range(sc, lc):
                #print('nowRow:{} nowCol:{}'.format(nowRow, nowCol))
                w_black = 0
                for idx2 in range(idx1):
                    if nowRow < ab[idx2][0] <= nowRow + 3 and nowCol < ab[idx2][1] <= nowCol + 3:
                        w_black += 1
                black_cnt[w_black]     -= 1
                black_cnt[w_black + 1] += 1
                #print(black_cnt)

for idx1 in range(len(black_cnt)):
    print(black_cnt[idx1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,N=map(int,input().split())
d=[]
for i in range(N):
    a,b=map(int,input().split())
    for j in range(-1,2):
        if not 1<a+j<H:
            continue
        for k in range(-1,2):
            if not 1<b+k<W:
                continue
            t=(a+j,b+k)
            d.append(t)
d.sort()
l=[0]*10
t=0
c=0
for i in d:
    if i==t:
        c+=1
    else:
        l[c]+=1
        t=i
        c=1
l[c]+=1
l[0]=(H-2)*(W-2)-sum(l)+1
print(*l,sep="\n")