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:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    target = set()
    res = [0] * 10
    for h, w in AB:
        cnt = 0
        flg = True
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                flg = False
            if (next_h, next_w) in AB:
                cnt += 1
            else:
                if (next_h, next_w) != (h, w):
                    target.add((next_h, next_w))
        if flg:
            res[cnt] += 1

    for h, w in target:
        cnt = 0
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                break
            if (next_h, next_w) in AB:
                cnt += 1
        else:
            res[cnt] += 1

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    target = set()
    res = [0] * 10
    for h, w in AB:
        cnt = 0
        flg = True
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                flg = False
            if (next_h, next_w) in AB:
                cnt += 1
            else:
                target.add((next_h, next_w))
        if flg:
            res[cnt] += 1

    for h, w in target:
        cnt = 0
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                break
            if (next_h, next_w) in AB:
                cnt += 1
        else:
            res[cnt] += 1

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
H, W, N = map(int, input().split())
L = []
for _ in range(N):
    a, b = map(int, input().split())
    L.append([a, b])

# 黒いマスからスタートして右下の3 * ３グリッドマスにたどり着きたい場合はこう！
d = defaultdict()
for i in range(N):
    for sx in range(3):
        for sy in range(3):
            if 3 <= L[i][0] + sx <= H and 3 <= L[i][1] + sy <= W:
                if (L[i][0] + sx, L[i][1] + sy) not in d:
                    d[(L[i][0] + sx, L[i][1] + sy)] = 1
                else:
                    d[(L[i][0] + sx, L[i][1] + sy)] += 1

# print(d)
c = Counter(d.values())
ans = [0 for _ in range(10)]

for k, v in c.items():
    if v > 0:
        ans[k] = v

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:

h,w,n = map(int,input().split())
d = {}
for i in range(n):
    a,b = map(int,input().split())
    a,b = a-1,b-1

    am1_f = a-1 > 0
    ap1_f = a+1 < h-1
    bm1_f = b-1 > 0
    bp1_f = b+1 < w-1
    a_f = a > 0 and a < h-1
    b_f = b > 0 and b < w-1

    am1 = a-1
    ap1 = a+1
    bm1 = b-1
    bp1 = b+1

    if am1_f:
        baseid = am1 * w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

    if ap1_f:
        baseid = ap1*w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    if a_f:

        baseid = a * w
        if b_f:
            pid = baseid + b
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    # print(d)

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

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

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

for a in ans:
    print(a)

Submission status: Accepted

Solution code:


h,w,n = map(int,input().split())
d = {}
for i in range(n):
    a,b = map(int,input().split())
    a,b = a-1,b-1

    am1_f = a-1 > 0
    ap1_f = a+1 < h-1
    bm1_f = b-1 > 0
    bp1_f = b+1 < w-1
    a_f = a > 0 and a < h-1
    b_f = b > 0 and b < w-1

    am1 = a-1
    ap1 = a+1
    bm1 = b-1
    bp1 = b+1

    if am1_f:
        baseid = am1 * w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

    if ap1_f:
        baseid = ap1*w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    if a_f:

        baseid = a * w
        if b_f:
            pid = baseid + b
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    # print(d)

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

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

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

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter

h,w,n = map(int,input().split())
d = {}
for i in range(n):
    a,b = map(int,input().split())
    a,b = a-1,b-1

    am1_f = a-1 > 0
    ap1_f = a+1 < h-1
    bm1_f = b-1 > 0
    bp1_f = b+1 < w-1
    a_f = a > 0 and a < h-1
    b_f = b > 0 and b < w-1

    am1 = a-1
    ap1 = a+1
    bm1 = b-1
    bp1 = b+1

    if am1_f:
        baseid = am1 * w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

    if ap1_f:
        baseid = ap1*w
        if b_f:
            pid = baseid + b

            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    if a_f:

        baseid = a * w
        if b_f:
            pid = baseid + b
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bm1_f:
            pid = baseid + bm1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1

        if bp1_f:
            pid = baseid + bp1
            if pid not in d:
                d[pid] = 1
            else:
                d[pid] += 1
    # print(d)

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

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

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

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import Counter

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

# 3*3マスの処理用リスト
dir = [[0, 0], [1, 0], [1, 1], [0, 1], [-1, 1],
       [-1, 0], [-1, -1], [0, -1], [1, -1]]

# そのマスを中心とする3*3グリッドに含まれる黒マスの数
dict = {}

for i in range(N):
    a, b = map(int, input().split())
    for dy, dx in dir:
        # 3*3グリッドは、H*Wの中に完全に含まれていなければならないことに注意
        if 2 <= a + dy <= H - 1 and 2 <= b + dx <= W - 1:
            if (a + dy, b + dx) not in dict:
                dict[(a + dy, b + dx)] = 1
            else:
                dict[(a + dy, b + dx)] += 1

c = Counter(dict.values())
ans = [0 for _ in range(10)]

# ans[1], ans[2], ..., ans[9]を確定させる（ans[0]は後述）
for k, v in c.items():
    if v > 0:
        ans[k] = v

# 全体で作れる3*3グリッドは(H-2)*(W-2)個
# ans[1],...,ans[9]の総和を引くとans[0]になる
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    """
    https://atcoder.jp/contests/abc045/submissions/14945636
    が高速に動作していたので参考に写経する。

    各黒マスに対して、それを含むテンプレートを左上の座標値で管理する。
    （写経元は右下座標で管理してる）
    このテンプレート及びそこに黒マスが何個入っているかを管理しておけば
    黒マス位置をソートして全体位置を把握していなくてもオンラインで更新が可能。
    """
    H, W, N = map(int, input().split())
    ans = [0] * 10
    templates = {}
    for _ in range(N):
        a, b = map(int, input().split())
        for i in range(9):
            # (h, w)がテンプレートの左上座標
            h, w = (a - 3) + i // 3, (b - 3) + i % 3
            if h < 0 or w < 0: continue
            if h > H - 3 or w > W - 3: continue
            idx = h * W + w
            if idx in templates:
                ans[templates[idx]] -= 1
                templates[idx] += 1
                ans[templates[idx]] += 1
            else:
                templates[idx] = 1
                ans[1] += 1
    ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
    for a in ans: print(a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    H, W, N = map(int, input().split())
    black = []
    d = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        black.append((a - 1, b - 1))
        d[a - 1].append(b - 1)
    for key in d: d[key].sort()

    ans = [0] * 10
    checked = set()
    # (a, b)がテンプレートのどこにいるかで９通り試す
    for i in range(9):
        for a, b in black:
            h, w = a - i // 3, b - i % 3
            if (h, w) in checked: continue
            if h < 0 or w < 0: continue
            if h > H - 3 or w > W - 3: continue
            cnt = 0
            idx1 = bisect_left(d[h], w)
            idx2 = bisect_left(d[h], w + 3)
            cnt += idx2 - idx1
            idx1 = bisect_left(d[h + 1], w)
            idx2 = bisect_left(d[h + 1], w + 3)
            cnt += idx2 - idx1
            idx1 = bisect_left(d[h + 2], w)
            idx2 = bisect_left(d[h + 2], w + 3)
            cnt += idx2 - idx1
            #print("({}, {})=>{}".format(h, w, cnt))
            ans[cnt] += 1
            checked.add((h, w))
    ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
    for a in ans: print(a)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
Draw = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Sq =  dd(lambda:0) #3*3正方形を左上のマスの座標で区別。値は正方形内の黒塗りの個数
In = lambda x,y:[(x-i,y-j) for i in range(3) for j in range(3) if 0<=x-i<H-2 and 0<=y-j<W-2] #塗りつぶしたマスを含む正方形の座標のリストを返す関数
for a,b in Draw:
    for x,y in In(a-1,b-1): 
        Sq[x,y] += 1 #Sqの更新
Ans = [(H-2)*(W-2)-len(Sq)] + [sum(v==i for v in Sq.values()) for i in range(1,10)]         
for ans in Ans:
    print(ans)

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
from collections import defaultdict as dd
Grid =  dd(lambda:0) #3*3正方形を左上のマスで区別。値は正方形内の黒塗りの個数
Draw = lambda x,y:[(x-i,y-j) for i in range(3) for j in range(3) if 0<=x-i<H-2 and 0<=y-j<W-2] #塗りつぶしたマスを含む正方形の座標のリストを返す関数
for _ in range(N):
    a, b = map(int, input().split())
    for x,y in Draw(a-1,b-1): #Gridの更新
        Grid[x,y] += 1
Ans = [(H-2)*(W-2)-len(Grid) if i == 0 else sum(v==i for v in Grid.values()) for i in range(10)]         
for ans in Ans:
    print(ans)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split());I=[list(map(int,input().split()))for i in[0]*n]
from itertools import product as p;from collections import Counter as c;ans=[0]*9;o=(h-2)*(w-2)
for k,v in c(c([(a-x)*w+b-y for x,y in p(range(3),repeat=2) for a,b in I if h-1>a-x>0<b-y<w-1]).values()).items():ans[k-1]=v;o-=v
print(o,*ans,sep='\n')

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split());from itertools import product as p;from collections import Counter as c;I=[list(map(int,input().split()))for i in[0]*n];ans=[0]*9
for k,v in c(c([(a-x)*w+b-y for x,y in p(range(3),repeat=2) for a,b in I if h-1>a-x>0<b-y<w-1]).values()).items():ans[k-1]=v
print((h-2)*(w-2)-sum(ans),*ans,sep='\n')

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
from itertools import product as pr
from collections import Counter as co
ans=[(h-2)*(w-2)]+[0]*9
io=[tuple(map(int,input().split())) for i in range(n)]
for k,v in co(co([(a-x)*w+b-y for x,y in pr(range(3),repeat=2) for a,b in io if h-1>a-x>0<b-y<w-1]).values()).items():
    ans[k]=v
    ans[0]-=v
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
spots=set([eval(input().replace(' ','*w+'))-w-1 for i in range(n)])
anss=[0]*10
from itertools import product as pr
moves=(tuple(x+w*y for x,y in pr(range(0,3),repeat=2)))
for i in spots:
    a,b=divmod(i,w)
    pre=[0]*9
    for x in range(max(0,a-2),min(h-2,a+1)):
        for y in range(max(0,b-2),min(w-2,b+1)):
            ind=w*x+y
            pre[x-a+(y-b)*3+8]+=sum(ind+m in spots for m in moves)
    for v in pre:anss[v]+=1
tans=[0]*10

ans0=(h-2)*(w-2)
for i in range(1,10):
    tans[i]=anss[i]//i
    ans0-=anss[i]//i
tans[0]=ans0
print(*tans,sep='\n')

Submission status: Accepted

Solution code:
def main():
	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])
if __name__ == '__main__':
	main()

Submission status: Accepted

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

while N:
  N-=1
  x,y = map(int,input().split())
  
  for i in range(9):
    a = (x+i%3,y+i//3)
    D[a] = D.get(a,0)+(H>=a[0]>2<a[1]<=W)

c = [list(D.values()).count(i+1) for i in range(9)]
print((H-2)*(W-2)-sum(c))

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

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    from itertools import product

    h, w, n = map(int, input().split())
    dic = {}
    for _ in range(n):
        a, b = map(int, input().split())
        a -= 2
        b -= 2
        for i in product([-1, 0, 1], repeat=2):
            aa = a + i[0]
            bb = b + i[1]
            if 0 <= aa <= h-3 and 0 <= bb <= w-3:
                try:
                    dic[(aa, bb)] += 1
                except:
                    dic[(aa, bb)] = 1

    ans = [0] * 10
    for i in dic.values():
        ans[i] += 1
    ans[0] = (h-2) * (w-2) - len(dic)

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]

itta={}
dic={}
for a,b in ab:
    dic[(a,b)]=1
def seek(t,y):
    if (not (t,y) in itta) and 2<=t<h and 2<=y<w:
        itta[(t,y)]=1
        cnt=0
        for i in range(3):
            for j in range(3):
                cnt+=(t-1+i,y-1+j) in dic
        return cnt
    else:
        return 0

lst=[0]*10
for i in range(n):
    a,b=ab[i]
    for i in range(3):
        for j in range(3):
            cnt=seek(a-1+i,b-1+j)
            if cnt:
                lst[cnt]+=1

# print(lst)
# sumlst=sum(lst)
lst[0]=(h-2)*(w-2)-sum(lst)
for i in range(10):
    print(lst[i])

Submission status: Accepted

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
    judge = dict()
    for _ in range(n):
        a, b = map(int, input().split())
        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 judge:
                    judge[(a+i, b+j)] += 1
                else:
                    judge[(a+i, b+j)] = 1
   
    ans = [0]*10
    
    for v in judge.values():
        ans[v] += 1
    ans[0] = (h-2)*(w-2)-sum(ans[1:])
    
    for a in ans:
        print(a)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

xy_pos = dict()

for i in range(n):
    a, b = map(int, input().split())
    for k in range(-2,1):
        for l in range(-2,1):
            x = (a-1) + k
            y = (b-1) + l
            if (0 <= x <=(h-1)-2) and (0 <= y <=(w-1)-2):
                xy = str(x) + "x" + str(y)
                if xy in xy_pos:
                    xy_pos[xy] += 1
                else:
                    xy_pos[xy] = 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

h,w,n=MI()
sq=defaultdict(int)
for _ in range(n):
    a,b=MI1()
    for i in range(max(0,a-2),min(h-2,a+1)):
        for j in range(max(0,b-2),min(w-2,b+1)):
            sq[i,j]+=1
cnt=[0]*10
for k,v in sq.items():cnt[v]+=1
cnt[0]=(h-2)*(w-2)-sum(cnt)
print(*cnt,sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.readline

h,w,n = map(int,input().split())
d = defaultdict()
ans = [0]*10

for k in range(n):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    for i in range(-1,2):
        for j in range(-1,2):
            if (a+i,b+j) in d:
                d[(a+i,b+j)] += 1
            else:
                d[(a+i,b+j)] = 1

for k,v in d.items():
    if 0 < k[0] < h-1 and 0 < k[1] < w-1:
        ans[v] += 1

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def add_memo(tate,yoko):
    global memo
    if 2 <= tate <= h-1:
        if 2 <= yoko <= w-1:
            memo.append([tate,yoko])

h,w,n = map(int,input().split())
#print(s)
memo = []
for i in range(0,n):
    x,y = map(int,input().split())
    add_memo(x-1,y-1)
    add_memo(x-1,y)
    add_memo(x-1,y+1)
    add_memo(x,y-1)
    add_memo(x,y)
    add_memo(x,y+1)
    add_memo(x+1,y-1)
    add_memo(x+1,y)
    add_memo(x+1,y+1)

memo.sort()
ans = [0] * 10
ans[0] = (h-2)*(w-2)
tmp_x = 0
tmp_y = 0
count = 0
for i in range(0,len(memo)):
    if tmp_x == memo[i][0] and tmp_y == memo[i][1]:
        ans[count] -= 1
        count += 1
        ans[count] += 1
    else:
        ans[0] -= 1
        count = 1
        ans[count] += 1
    tmp_x = memo[i][0]
    tmp_y = memo[i][1]
#    print(memo[i],count)

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,n = list(map(int, input().split()))
from collections import defaultdict, Counter
d = defaultdict(int)
for i in range(n):
    a,b = map(int, input().split())
    for i in range(a-2, a+1):
        for j in range(b-2, b+1):
            if 1<=i<=h-2 and 1<=j<=w-2:
                d[i,j] += 1
ans = [None]*10
ans[0] = (h-2)*(w-2) - len(d)
c = Counter(d.values())
for i in range(1,10):
    if i in c:
        ans[i] = c[i]
    else:
        ans[i] = 0
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

H,W,N = MI()

from collections import defaultdict,Counter

d = defaultdict(int)  # d[(i,j)] = [i,i+2]×[j,j+2] に黒いマスが何個あるか
for i in range(N):
    a,b = MI()
    for j in range(max(1,a-2),min(a,H-2)+1):
        for k in range(max(1,b-2),min(b,W-2)+1):
            d[(j,k)] += 1

c = Counter(list(d.values()))
print((H-2)*(W-2)-sum(c.values()))
for i in range(1,10):
    print(c[i])

Submission status: Accepted

Solution code:
H,W,N=map(int,input().split())
s=set()
for i in range(N):
    a,b=map(lambda x:int(x)-1,input().split())
    s.add((a,b))
count=[0]*10

for x,y in s:
    for tx in range(x-2,x+1):
        for ty in range(y-2,y+1):
            if tx<0 or ty<0 or tx+2>=H or ty+2>=W:
                continue
            cnt=0
            for nx in range(tx,tx+3):
                for ny in range(ty,ty+3):
                    if (nx,ny) in s:
                        cnt+=1
            count[cnt]+=1
count=[0]+[count[i]//i for i in range(1,10)]
count[0]=(H-2)*(W-2)-sum(count)
print(*count,sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]
from collections import defaultdict
dic = defaultdict(lambda: 0)
for y,x in AB:
    for dx in range(-1,2):
        for dy in range(-1,2):
            nx,ny = x+dx,y+dy
            if not 1 <= nx <= W: continue
            if not 1 <= ny <= H: continue
            dic[(nx,ny)] += 1

ans = [0] * 10
for (x,y),c in dic.items():
    if x==1 or x==W or y==1 or y==H: continue
    ans[c] += 1
s = sum(ans)
ans[0] = (W-2)*(H-2)-s

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
  H, W, N = map(int, input().split())
  ans = [0]*10
  dic = defaultdict(lambda: defaultdict(lambda: 0))
  for i in range(N):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    for i in range(x-1,x+2):
      for j in range(y-1,y+2):
        if i>0 and i<H-1 and j>0 and j<W-1:
          if dic[i][j]>0:
            ans[dic[i][j]] -= 1
          dic[i][j] += 1
          ans[dic[i][j]] += 1
  total = (H-2)*(W-2)
  ans[0] = total - sum(ans[1:])
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

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

H,W,N = map(int,readline().split())
from collections import defaultdict

# 9x9のマスの左上のマスの座標をキーにして、各正方形の黒マス数をdictionaryで管理
# 10 ** 5 * 9程度

dic = defaultdict(int)

for i in range(N):
  a,b = map(int,readline().split())
  a,b = a - 1,b - 1
  for A in range(max(0,a - 2), min(a + 1,H - 2)):
    for B in range(max(0,b - 2), min(b + 1,W - 2)):
      dic[(A,B)] += 1

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

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

for a in ans:
  print(a)

Submission status: Accepted

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

H,W,N = map(int,readline().split())
from collections import defaultdict

# 9x9のマスの左上のマスの座標をキーにして、各正方形の黒マス数をdictionaryで管理
# 10 ** 5 * 9程度

dic = defaultdict(int)

for i in range(N):
  a,b = map(int,readline().split())
  a,b = a - 1,b - 1
  for A in range(max(0,a - 2), min(a + 1,H - 2)):
    if A < 0:
      continue
    for B in range(max(0,b - 2), min(b + 1,W - 2)):
      if B < 0:
        continue
      dic[(A,B)] += 1

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

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

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
from collections import Counter
h, w, n = map(int, input().split())
c = Counter([])

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

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

ans = [0] * 10
total = 0
for k, v in c.items():
    ans[v]+=1
    total+=1
ans[0]=(h-2)*(w-2) - total


for a in ans:
    print(a)

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):
      x=a+p
      y=b+q
      if 2<=x<=H-1 and 2<=y<=W-1:
        pos=(x,y)
        if pos in D:
          D[pos]+=1
        else:
          D[pos]=1
ans=[0]*10
V=list(D.values())
for v in V:
  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())
X = [list(map(int,input().split())) for _ in range(N)]
C = {}
for i in range(N):
    a,b = X[i]
    if a-2>=1 and b-2>=1:
        if (a-2,b-2) not in C:
            C[(a-2,b-2)] = 0
        C[(a-2,b-2)] += 1
    if a-2>=1 and b-1>=1 and b+1<=W:
        if (a-2,b-1) not in C:
            C[(a-2,b-1)] = 0
        C[(a-2,b-1)] += 1
    if a-2>=1 and b+2<=W:
        if (a-2,b) not in C:
            C[(a-2,b)] = 0
        C[(a-2,b)] += 1
    if a-1>=1 and b-2>=1 and a+1<=H:
        if (a-1,b-2) not in C:
            C[(a-1,b-2)] = 0
        C[(a-1,b-2)] += 1
    if a-1>=1 and b-1>=1 and a+1<=H and b+1<=W:
        if (a-1,b-1) not in C:
            C[(a-1,b-1)] = 0
        C[(a-1,b-1)] += 1
    if a-1>=1 and a+1<=H and b+2<=W:
        if (a-1,b) not in C:
            C[(a-1,b)] = 0
        C[(a-1,b)] += 1
    if b-2>=1 and a+2<=H:
        if (a,b-2) not in C:
             C[(a,b-2)] = 0
        C[(a,b-2)] += 1
    if b-1>=1 and a+2<=H and b+1<=W:
        if (a,b-1) not in C:
            C[(a,b-1)] = 0
        C[(a,b-1)] += 1
    if a+2<=H and b+2<=W:
        if (a,b) not in C:
            C[(a,b)] = 0
        C[(a,b)] += 1
D = {i:0 for i in range(10)}
for c in C:
    D[C[c]] += 1
cnt = 0
for i in range(1,10):
    cnt += D[i]
D[0] = (H-2)*(W-2)-cnt
for i in range(10):
    print(D[i])

Submission status: Accepted

Solution code:
H,W,N = map(int,input().split())
B = set([])
for i in range(N):
  a,b = map(int,input().split())
  a-=1;b-=1
  B.add((a,b))
#print(B)
BB = list(B)
ans = [0 for _ in range(10)]
for i in range(N):
  cnt = 0; temp = 0
  x,y = BB[i]
  #print(x,y)
  for sx in range(max(0,x-2),min(x,H-3)+1):
    for sy in range(max(0,y-2),min(y,W-3)+1):
      temp = 0
      for p in range(3):
        for q in range(3):
          if (sx+p,sy+q) in B:
            temp += 1
      #print(sx,sy,temp)
      ans[temp] += 1
for i in range(1,10):
  ans[i] = ans[i]//i
ans[0] = (H-2)*(W-2)-sum(ans[1:])
for t in ans:
  print(t)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
dic={}
INF=10**10
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*INF+k in dic:
        dic[j*INF+k]+=1
      else:
        dic[j*INF+k]=1
ans=[0]*10
ans[0]=(h-2)*(w-2)
for i in dic:
  ans[0]-=1
  ans[dic[i]]+=1
for i in ans:
  print(i)