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: Accepted

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

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

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

H, W, N = map(int, input().split())
query = [list(map(int, input().split())) 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]
        star_list.add((nx, ny))

star_list = list(star_list)
for x, y in star_list:
    if not (x <= 0 or W - 1 <= x or y <= 0 or H - 1 <= y):
        lista[counter(x, y)] += 1

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

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
D=dict()
for i in range(n):
    a,b=map(int,input().split())
    for p in range(-1,2):
        for q in range(-1,2):
            aa=a+p
            bb=b+q
            if 2<=aa<=h-1 and 2<=bb<=w-1:
                aabb=str(aa)+"_"+str(bb)
                if aabb in D:
                    D[aabb]+=1
                else:
                    D[aabb]=1
ans=[0]*10
V=list(D.values())
for v in V:
    ans[v]+=1
ans[0]=(h-2)*(w-2)-sum(ans)
for i in range(10):
    print(ans[i])

Submission status: Accepted

Solution code:
import collections
from itertools import product

H, W, N = map(int,input().split())
PaintList = []
pat = list(product((-2,-1,0),repeat=2))
for i in range(N):
  x,y = map(int, input().split())
  for p in pat:
    xw = x + p[0]
    yw = y + p[1]
    #print(xw,yw)
    if 1 <= xw <= H-2 and 1 <= yw <= W-2:
      PaintList.append((xw,yw))

c = collections.Counter(PaintList)
#print(c)
ans = [0] * 10
for k,v in c.items():
  if k[0] <= H-2 and k[1] <= W-2:
    ans[v] += 1
  
ans[0] = (H-2)*(W-2) - sum(ans[1:10])
 
for i in range(10):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

H, W, N = map(int, input().split())
X = (H - 2) * (W - 2)

A = defaultdict(int)
for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for p in range(3):
        for q in range(3):
            k, l = a - p, b - q
            if k < 0 or k >= H or l < 0 or l >= W:
                continue
            if k + 2 >= H or l + 2 >= W:
                continue
            A[(k, l)] += 1

ans = [0] * 10
for k, v in A.items():
    ans[v] += 1
ans[0] = X - sum(ans)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys

def getsqs(coor,h,w):
    l=[coor[0]+x+h*(coor[1]+y-1) for x in range(-1,2) for  y in range(-1,2) \
        if coor[0]+x>1 and coor[0]+x<h and coor[1]+y>1 and coor[1]+y<w]
    return l

def main(h,w,coords):
    sq=[]
    ans=[0 for _ in range(10)]
    for coor in coords:
        sq.extend(getsqs(coor,h,w))
#        print(coor,getsqs(coor,h,w))
    sq.sort()
    sq.append(h*w)
    ind=0
    for x in range(len(sq)-1):
        if sq[x+1]-sq[x]!=0:
            ans[x-ind+1]+=1
            ind=x+1
    ans[0]=max(0,(h-2)*(w-2)-sum(ans))
    return ans

h,w,n=map(int,sys.stdin.readline().strip().split())
coords=[list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)]

for x in main(h,w,coords):
    print(x)

Submission status: Accepted

Solution code:
def main():
    H, W, N = map(int, input().split())
    s = set()
    for _ in range(N):
        a, b = map(int, input().split())
        s.add((a,b))
    u = set()
    r = [0] * 10
    def search(ii, jj):
        t = 0
        for x in range(-1, 2):
            for y in range(-1, 2):
                xt = x + ii
                yt = y + jj
                if (x+ii, y+jj) in s:
                    t += 1
        r[t] += 1
    for t in s:
        for x in range(-1, 2):
            for y in range(-1, 2):
                xt = x + t[0]
                yt = y + t[1]
                if xt < 2 or yt < 2 or xt > H-1 or yt > W-1:
                    continue
                if (xt, yt) in u:
                    continue
                u.add((xt, yt))
                search(xt, yt)
    r[0] = (H-2) * (W-2) - len(u)
    for i in range(10):
        print(r[i])
main()

Submission status: Accepted

Solution code:
def main():
    H, W, N = map(int, input().split())
    C = {}
    for _ in range(N):
        a, b = map(int, input().split())
        for x in range(max(2, a - 1), min(H, a + 2)):
            for y in range(max(2, b - 1), min(W, b + 2)):
                C[(x, y)] = C.get((x, y), 0) + 1
    D = list(C.values())
    print((H - 2) * (W - 2) - len(C))
    for j in range(1, 10):
        print(D.count(j))

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.buffer.readline

count = defaultdict(lambda: 0)

H, W, N = map(int, input().split())
for _ in range(N):
    a, b = map(int, input().split())
    for a_2 in range(a-1, a+2):
        for b_2 in range(b-1, b+2):
            if 2 <= a_2 <= H-1 and 2 <= b_2 <= W-1:
                count[a_2, b_2] += 1

ans = [0] * 10
for _, v in count.items():
    ans[v] += 1

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

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

Submission status: Accepted

Solution code:
h, w, n = map(int, input().split())
d = dict()
ans = [0] * 10
for _ in range(n):
    a, b = map(int, input().split())
    for i in range(-1, 2):
        for j in range(-1, 2):
            x, y = a + i, b + j
            if 1 < x < h and 1 < y < w:
                k = x * w + y
                if not k in d:
                    d[k] = 1
                    ans[1] += 1
                else:
                    ans[d[k]] -= 1
                    ans[d[k] + 1] += 1
                    d[k] += 1
ans[0] = (h - 2) * (w - 2) - sum(ans)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict
    h, w, n = map(int, readline().split())
    c = defaultdict(int)
    count = [0] * 10
    count[0] = (h - 2) * (w - 2)

    for _ in range(n):
        a, b = map(int, readline().split())
        a, b = a - 1, b - 1
        for row in range(max(2, a), min(h - 1, a + 2) + 1):
            for col in range(max(2, b), min(w - 1, b + 2) + 1):
                cur = c[(row, col)]
                count[cur] -= 1
                count[cur + 1] += 1
                c[(row, col)] += 1

    print(*count, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	h, w, n = LI()
	black_points = []
	for i in range(n):
		a, b = LI()
		add_list = ((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))
		for c, d in add_list:
			if 1 <= c <= h-2 and 1 <= d <= w-2:
				black_points.append((c,d))
	counter = Counter(black_points)
	count_list = list(counter.values())
	counter2 = Counter(count_list)
	ans_list = [counter2[i] for i in range(1,10)]
	ans_list = [(h-2)*(w-2)-sum(ans_list)] + ans_list
	for ans in ans_list:
		print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(a,b,ans):
    z = d[a][b]
    for p in range(3):
        for q in range(3):
            if a-2+p<0 or a+p>=h or b-2+q<0 or b+q>=w:
                continue
            ok = True
            reachorig = False
            v = 0
            for i in range(3):
                for j in range(3):
                    if p+i==q+j==2:
                        reachorig = True
                    if z[p+i][q+j]==1:
                        if reachorig:
                            v += 1
                        else:
                            ok = False
                            break
            if ok:
                ans[v] += 1

h,w,n = inm()
d = {}
ab = []
for i in range(n):
    a,b = inm()
    a -= 1
    b -= 1
    ab.append((a,b))
    if a not in d:
        d[a] = {}
    d[a][b] = [[0]*5 for j in range(5)]
    d[a][b][2][2] = 1
for a,b in ab:
    for dx in range(-2,3):
        for dy in range(-2,3):
            if a+dx in d and b+dy in d[a+dx] and not (dx==dy==0):
                d[a+dx][b+dy][2-dx][2-dy] = 1

if False and DBG:
    for i in range(h):
        for j in range(w):
            if i in d and j in d[i]:
                #print(f"{i=} {j=}")
                for k in range(5):
                    print(d[i][j][k])
ans = [0]*10
for a,b in ab:
    foo(a,b,ans)
print((h-2)*(w-2)-sum(ans))
for i in range(1,10):
    print(ans[i])

Submission status: Accepted

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

from collections import deque,defaultdict,Counter
def main():
    H,W,N = map(int,input().split())
    point = [tuple(map(int,input().split())) for _ in range(N)]
    ans = [0] * 10

    dic = defaultdict(int)
    for p,q in point:
        for dy in (-1,0,1):
            for dx in (-1,0,1):
                if p + dy <= 1 or p + dy >= H:
                    continue
                if q + dx <= 1 or q + dx >= W:
                    continue
                center = (p + dy,q + dx)
                ans[dic[center]] -= 1
                dic[center] += 1
                ans[dic[center]] += 1
    ans[0] += (H - 2)*(W - 2)
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
dct=defaultdict(int)
ans={i:0 for i in range(10)}
ans[0]=(h-2)*(w-2)
for a,b in ab:
  a-=1
  b-=1
  u=max(0,a-2)
  d=min(h-3,a)
  l=max(0,b-2)
  r=min(w-3,b)
  for i in range(u,d+1):
    for j in range(l,r+1):
      ans[dct[(i,j)]]-=1
      dct[(i,j)]+=1
      ans[dct[(i,j)]]+=1
for i in range(10):
  print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, N = map(int,input().split())
d = defaultdict(int)
ta = [1,1,0,-1,-1,-1,0,1,0]
tb = [0,1,1,1,0,-1,-1,-1,0]

for _ in range(N):
    a, b = map(int,input().split())
    for i in range(9):
        na = a + ta[i]
        nb = b + tb[i]
        if 1 <= na <= H and 1 <= nb <= W:
            d[(na, nb)] += 1

ans = [0] * 10

for i, v in d.items():
    if 2 <= i[0] <= H-1 and 2 <= i[1] <= W-1:
        ans[v] += 1

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

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

Submission status: Accepted

Solution code:
h, w, n = map(int, input().split())
lst = []
for i in range(n):
    ai, bi = map(int, input().split())
    lst.append((ai, bi))

dic = {}
for i in range(10): dic[i] = 0
dic[0] = (h-2) * (w-2)
already = set([])
idx = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 0], [0, 1], [1, -1], [1, 0], [1, 1]]
for i in range(n):
    ai, bi = lst[i]
    for surround in idx:
        center = [ai+surround[0], bi+surround[1]]
        if min(center) < 2 or center[0] > h-1 or center[1] > w-1: continue
        cnt = 0
        for ind in idx:
            cell = (center[0]+ind[0], center[1]+ind[1])
            if cell in already: cnt += 1
        dic[cnt] -= 1
        dic[cnt+1] += 1
    already.add((ai, bi))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict,Counter

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

dic = defaultdict(int)

for _ in range(n):
    y,x= map(int,input().split())
    for i,j in product([-1,0,1],repeat=2):
        nx = x+i
        ny = y+j
        if 2 <= nx <= w-1 and 2 <= ny <= h-1:
            dic[nx,ny] += 1

c = Counter(dic.values())
c[0] = (w-2)*(h-2)-sum(c.values())

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect

h,w,n=map(int,input().split())
d={}
p=((1,1),(1,0),(1,-1),(0,1),(0,0),(0,-1),(-1,1),(-1,0),(-1,-1))
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for idx in p:
        s,t=idx
        if 0<a+s<h-1 and 0<b+t<w-1:
          if (a+s,b+t) not in d:
            d[(a+s,b+t)]=1
          else:
            d[(a+s,b+t)]+=1
ans=[0]*10
for x in d.values():
  ans[x]+=1
ans[0]=(h-2)*(w-2)-sum(ans)
print(*ans)

Submission status: Accepted

Solution code:
a={}
h,w,n=map(int,input().split())
for i in range(n):
  y,x=map(int,input().split())
  for j in range(max(2,x-1),min(w-1,x+1)+1):
    for k in range(max(2,y-1),min(h-1,y+1)+1):
      if j*(10**10)+k in a:
        a[j*(10**10)+k]+=1
      else:
        a[j*(10**10)+k]=1
ans=[0]*10
ans[0]=(h-2)*(w-2)
for key in a:
  ans[0]-=1
  ans[a[key]]+=1
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

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

covered = defaultdict(int)
vector = [[-1,-1],[-1,0],[-1,1],[1,0],[1,1],[0,0],[0,-1],[0,1],[1,-1]]

for _ in range(N):
    a,b = map(int,input().split())
    for dx,dy in vector:
        x = a+dx-1
        y = b+dy-1
        if 1 <= x < H-1 and 1 <= y < W-1:
            covered[(x,y)] += 1

values = [0]*10
for i in covered.values():
    values[i] += 1

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

for v in values:
    print(v)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    H, W, N = map(int, input().split())
    C = defaultdict(int)
    for _ in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        for h in range(3):
            for w in range(3):
                if 0 <= a-h < H - 2 and 0 <= b-w < W - 2:
                    C[(a-h, b-w)] += 1
    
    ans = [0] * 10
    s = 0
    for key in C:
        ans[C[key]] += 1
        s += 1
    ans[0] = ((H - 2) * (W - 2) - s)
    print(*ans, sep="\n") 
    #print(C)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

H, W, N = map(int, input().split())
cnt = defaultdict(int)
D = tuple(product((-1, 0, 1), repeat=2))

for _ in range(N):
    a, b = map(int, input().split())
    for dh, dw in D:
        h = a + dh
        w = b + dw
        if 2 <= h <= H - 1 and 2 <= w <= W - 1:
            cnt[(h, w)] += 1

ans = [0] * 10
for c in cnt.values():
    ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W, N = NMI()
    grid = {}
    for i in range(N):
        a, b = NMI()
        for t in range(-2, 1):
            for k in range(-2, 1):
                if a + t < 1 or b + k < 1:
                    continue
                if a + t >= H - 1 or b + k >= W - 1:
                    continue
                point = (a+t) * 10**10 + b+k
                grid[point] = grid.get(point, 0) + 1
    c = Counter(grid.values())
    for i in range(10):
        if i == 0:
            print((H-2)*(W-2) - sum(c.values()))
        else:
            print(c.get(i, 0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    H, W, N = list(map(int, input().split(' ')))
    coord_list = [list(map(int, input().split(' '))) for _ in range(N)]
    # count squares (key: coord of top left cell, value: number of appearance)
    square_count = defaultdict(int)
    for coord in coord_list:
        coord = tuple(coord)
        # black cell is located on the top row
        if coord[0] + 2 <= H and coord[1] + 2 <= W:
            square_count[coord] += 1
        if coord[0] + 2 <= H and 1 <= coord[1] - 1 and coord[1] + 1 <= W:
            square_count[(coord[0], coord[1] - 1)] += 1
        if coord[0] + 2 <= H and 1 <= coord[1] - 2:
            square_count[(coord[0], coord[1] - 2)] += 1
        # black cell is located in the middle row
        if 1 <= coord[0] - 1 and coord[0] + 1 <= H and coord[1] + 2 <= W:
            square_count[(coord[0] - 1, coord[1])] += 1
        if 1 <= coord[0] - 1 and coord[0] + 1 <= H and 1 <= coord[1] - 1 and coord[1] + 1 <= W:
            square_count[(coord[0] - 1, coord[1] - 1)] += 1
        if 1 <= coord[0] - 1 and coord[0] + 1 <= H and 1 <= coord[1] - 2:
            square_count[(coord[0] - 1, coord[1] - 2)] += 1
        # black cell is located on the bottom row
        if 1 <= coord[0] - 2 and coord[1] + 2 <= W:
            square_count[(coord[0] - 2, coord[1])] += 1
        if 1 <= coord[0] - 2 and 1 <= coord[1] - 1 and coord[1] + 1 <= W:
            square_count[(coord[0] - 2, coord[1] - 1)] += 1
        if 1 <= coord[0] - 2 and 1 <= coord[1] - 2:
            square_count[(coord[0] - 2, coord[1] - 2)] += 1
    # remove duplicated counts
    count = defaultdict(int)  # key: number of black cells, value: number of squares
    for v in square_count.values():
        count[v] += 1
    count_white_only = (H - 2) * (W - 2) - sum(count.values())
    count[0] = count_white_only
    # print answer
    for c in range(0, 10):
        print(count[c])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for _ in range(n):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    for i in range(-1, 2):
        for j in range(-1, 2):
            if 0 < a + i < h - 1 and 0 < b + j < w - 1:
                if (a+i, b+j) not in cnt:
                    cnt[(a+i, b+j)] = 0
                cnt[(a+i, b+j)] += 1

ans = {i: 0 for i in range(10)}
ans[0] = (h - 2) * (w - 2)
for _, x in cnt.items():
    ans[x] += 1
    ans[0] -= 1

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

Submission status: Accepted

Solution code:
h, w, n = map(int, input().split())
from collections import defaultdict
d = defaultdict(int)
surround = [(0, 0), (1,1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1)]
for _ in range(n):
    x, y  = map(int, input().split())
    x -= 1
    y -= 1
    for i in surround:
        if x + i[0] >= h or x + i[0] < 0 or y + i[1] < 0 or y + i[1] >= w:
            continue
        else:
            d[(x+i[0], y + i[1])] += 1
num = [0]*10
for key in d:
    if key[0] >= 1 and key[0] < h -1 and key[1] >= 1 and key[1] < w-1:
        num[d[key]] += 1

num[0] = (h-2)*(w-2) - sum(num)

for ans in num:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

for _ in range(n):
    a,b = map(int,input().split())

    for i in range(-1,2):
        for j in range(-1,2):
            if 1 < a+i < h and 1 < b+j < w:
                d[(a+i,b+j)] += 1

ans = [0]*10

for i in d.values():
    ans[i] += 1

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	H, W, N = tin()
	#s = input()
	dd=defaultdict(lambda : 0)
	for _ in range(N):
		a, b = tin()
		for da in range(3):
			for db in range(3):
				if a - da <= 0 or b - db <= 0:
					continue
				if a - da > H -2 or b -db > W-2:
					continue
				ii = (a - da)*(W+1)+(b - db)
				dd[ii]+=1
	
	nn = [0]*10
	for k in dd:
		nn[dd[k]]+=1
	nn[0]=((H-2)*(W-2))-sum(nn[1:])
	for v in nn:
		print(v)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    import sys
    input = sys.stdin.readline

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

    g = defaultdict(int)
    for _ in range(N):
        a, b = (int(x) - 1 for x in input().split())
        for i in range(3):
            if a - i < 0: continue
            if a - i + 3 > H: continue
            for j in range(3):
                if b - j < 0: continue
                if b - j + 3 > W: continue
                g[(a - i) * W + (b - j)] += 1
                # (a,b)を塗ったとき影響される3x3マス目の左上の座標に加算する

    ctr = [0] * 10
    tot = (H - 2) * (W - 2)
    for cnt in g.values():
        ctr[cnt] += 1
        tot -= 1
    ctr[0] = tot

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
参考(神様)
https://atcoder.jp/contests/abc045/submissions/6046010
"""

###かぶるやつを考える.例えばあるマスのかぶり値が9だとしたら,
###周囲はすべて黒->j=9のが1つとカウントしてよい,他の値についても同様.

import sys
from collections import defaultdict,Counter

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

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

covered = defaultdict(int)
vector = [(0,0),(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)]

for _ in range(N):
    a,b = map(int,input().split())

    for i,j in vector:
        x = a+i-1
        y = b+j-1

        if 0 < x < H-1 and 0 < y < W-1:
            covered[(x,y)] += 1

num = Counter(covered.values())
##print(num)
num[0] = (H-2)*(W-2)-sum(num.values())

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

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

m = {}

for i in range(N):
    a, b = map(int, input().split())
    for j in range(-2, 1):
        for k in range(-2, 1):
            if not 1 <= a + j <= H - 2 or not 1 <= b + k <= W - 2:
                continue
            m[(a + j, b + k)] = m.get((a + j, b + k), 0) + 1

ans = [0] * 10

for k, v in m.items():
    ans[v] += 1


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

Submission status: Accepted

Solution code:
H, W, N = [int(v) for v in input().split()]
points = (map(int, input().split()) for _ in range(N))
memory = {}
for ai, bi in points:
    for i in range(max(2, ai - 1), min(H - 1, ai + 1) + 1):
        for j in range(max(2, bi - 1), min(W - 1, bi + 1) + 1):
            key = (i, j)
            if not key in memory:
                memory[key] = 0
            memory[key] += 1

counter = {i: 0 for i in range(1, 10)}
for v in memory.values():
    counter[v] += 1

print((H - 2) * (W - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])

Submission status: Accepted

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

allcase=(H-2)*(W-2)

abset=set()
for _ in range(N):
  a,b=map(int,input().split())
  abset.add((a-1,b-1))
#print(abset)

memo=defaultdict(int)
for a,b in abset:
  for j in range(-2,1):
    if a+j<0 or H-2<=a+j:
      continue    
    for k in range(-2,1):
      if b+k<0 or W-2<=b+k:
        continue
      memo[(a+j,b+k)]+=1
#print(memo)  

case_list=[0]*10
for v in memo.values():
  case_list[v]+=1
case_list[0]=allcase-sum(case_list[1:])
#print(case_list)

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

Submission status: Accepted

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

allcase=(H-2)*(W-2)

abset=set()
for _ in range(N):
  a,b=map(int,input().split())
  abset.add((a-1,b-1))
#print(abset)

memo={}
def count_black(x,y):
  if (x,y) in memo:
    return memo[(x,y)]
  
  num_black=0
  for ii in range(3):
    for jj in range(3):
      if (x+ii,y+jj) in abset:
        num_black+=1
        
  memo[(x,y)]=num_black
  return num_black

case_list=[0]*10
for a,b in abset:
  for j in range(3):
    if a-j<0 or H-2<=a-j:
      continue    
    for k in range(3):
      if b-k<0 or W-2<=b-k:
        continue
      count_black(a-j,b-k)
#print(memo)  

case_list=[0]*10
for v in memo.values():
  case_list[v]+=1
case_list[0]=allcase-sum(case_list[1:])
#print(case_list)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline
h, w, n = map(int, input().split())
count = defaultdict(int)
# 3＊3の左上の位置でカウント
for i in range(n):
    a, b = map(int, input().split())
    for s in range(3):
        if a + s - 2 < 1 or a + s - 2 > h - 2:
            continue
        for t in range(3):
            if b - 2 + t < 1 or b - 2 + t > w - 2:
                continue
            count[(a - 2 + s, b - 2 + t)] += 1
ans = [0] * 10
for key, val in count.items():
    ans[val] += 1
ans[0] = (h - 2) * (w - 2) - sum(ans[1:])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict

h, w, n = map(int, input().split())
count = defaultdict(int)
# 3＊3の左上の位置でカウント
for i in range(n):
    a, b = map(int, input().split())
    for s in range(3):
        if a + s - 2 < 1 or a + s - 2 > h - 2:
            continue
        for t in range(3):
            if b - 2 + t < 1 or b - 2 + t > w - 2:
                continue
            count[(a - 2 + s, b - 2 + t)] += 1
ans = [0] * 10
for key, val in count.items():
    ans[val] += 1
ans[0] = (h - 2) * (w - 2) - sum(ans[1:])
print(*ans, sep="\n")

Submission status: Accepted

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

A = {}
for i in range(N):
  a,b = map(int,input().split())
  a-=1;b-=1
  for t in range(3):
    for s in range(3):
      if 0<=a-t<H-2 and 0<=b-s<W-2:
        if (a-t,b-s) not in A:
          A[(a-t,b-s)]  = 1
        else:
          A[(a-t,b-s)]  += 1
#print(A)
ans = [-1]
temp = list(A.values())
total = 0
for i in range(1,10):
  c = temp.count(i)
  total += c
  ans.append(c)
ans[0] = (H-2)*(W-2)-total
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from itertools import product
from collections import Counter

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

cnt = Counter()
for a, b in AB:
    for h, w in D:
        if 2 <= a + h <= H - 1 and 2 <= b + w <= W - 1:
            cnt[(a + h, b + w)] += 1

ans = [0] * 10
for c in cnt.values():
    ans[c] += 1

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