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:
#!/usr/bin/env python3
#ABC45 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

h,w,n = map(int,input().split())
f = defaultdict(lambda : 0)
for _ in range(n):
    a,b = map(int,input().split())
    if a-2 >= 1 and b-2 >= 1:
        f[(a-2,b-2)] += 1
    if a-2 >= 1 and b-1 >= 1 and b+1 <= w:
        f[(a-2,b-1)] += 1
    if a-2 >= 1 and b+2 <= w:
        f[(a-2,b)] += 1
    if a-1 >= 1 and b-2 >= 1 and a+1 <= h:
        f[(a-1,b-2)] += 1
    if a-1 >= 1 and b-1 >= 1 and a+1 <= h and b+1 <= w:
        f[(a-1,b-1)] += 1
    if a-1 >= 1 and b+2 <= w and a+1 <= h:
        f[(a-1,b)] += 1
    if a+2 <= h and b-2 >= 1:
        f[(a,b-2)] += 1
    if a+2 <= h and b-1 >= 1 and b+1 <= w:
        f[(a,b-1)] += 1
    if a+2 <= h and b+2 <= w:
        f[(a,b)] += 1
ans = [0]*10
cnt = 0
for i in f.values():
    ans[i] += 1
    cnt += 1
ans[0] = (h-2)*(w-2) - cnt
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for p in range(25):
        i,j=p//5,p%5
        if 0<a+i-2<=h and 0<b+j-2<=w:
            if (a+i-2)*(10**9)+b+j-3 in ab_d:
                temp[i*5+j]=1
            else:
                temp[i*5+j]=0
    for p in range(9):
        i,j=p//3,p%3
        cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
        if None not in cnt:
            ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
ans=[len(ans[i]) for i in range(9)]

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(W: int, H: int, N: int, a: "List[int]", b: "List[int]"):
    ret = [0] * 10
    ret[0] = (H - 2) * (W - 2)
    reduces = []
    for i in range(N):
        lx = max(0, a[i] - 3)
        rx = min(W - 2, a[i])
        ly = max(0, b[i] - 3)
        ry = min(H - 2, b[i])
        for bx in range(lx, rx):
            for by in range(ly, ry):
                reduces.append((bx, by))
    reduces.sort()
    cnt = 1
    for i in range(1, len(reduces)):
        if reduces[i] == reduces[i - 1]:
            cnt += 1
        else:
            ret[0] -= 1
            ret[cnt] += 1
            cnt = 1
    if len(reduces):
        ret[0] -= 1
        ret[cnt] += 1
    for r in ret:
        print(r)
    return


def _solve(W: int, H: int, N: int, a: "List[int]", b: "List[int]"):
    ret = [0] * 10
    ret[0] = (H - 2) * (W - 2)
    reduces = []
    for i in range(N):
        lx = max(0, a[i] - 3)
        rx = min(W - 2, a[i])
        ly = max(0, b[i] - 3)
        ry = min(H - 2, b[i])
        for bx in range(lx, rx):
            for by in range(ly, ry):
                cnt = 0
                for x in range(0, 3):
                    for y in range(0, 3):
                        #print(a[i] - 1, b[i] - 1, bx + x, by + y)
                        if grid[by + y][bx + x]:
                            cnt += 1
                ret[cnt] -= 1
                ret[cnt + 1] += 1
        #print(b[i] - 1, a[i] - 1, H, W)
        grid[b[i] - 1][a[i] - 1] = True
    for r in ret:
        print(r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(H, W, N, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in [0]*N]

d = {}
for a,b in ab:
    for da in (-1,0,1):
        for db in (-1,0,1):
            if not ( 2<=a+da<=H-1 and 2<=b+db<=W-1):continue
            d[(a+da,b+db)] = d.get((a+da,b+db),0)+1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
H, W, N = map(int, input().split())
cnt = defaultdict(lambda : 0)
for i in range(N):
    a, b = map(lambda x: int(x)-1, input().split())
    for y in range(a-2, a+1):
        for x in range(b-2, b+1):
            if 0 <= y < H-2 and 0 <= x < W-2:
                cnt[(y, x)] += 1
ans = [0] * 10
for key in cnt:
    ans[cnt[key]] += 1
ans[0] += ans[0] + (H-2) * (W-2) - len(cnt)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mem = defaultdict(int)
for _ in range(N) :
    a, b = map(int, input().split())
    for i in range(max(2, a-1), min(H-1, a+1)+1) :
        for j in range(max(2, b-1), min(W-1, b+1)+1) :
            mem[(i, j)] += 1
            
ret = [0] * 10
for k, v in mem.items() :
    ret[v] += 1

ret[0] = (H - 2) * (W - 2) - sum(ret)
 
for r in ret :
    print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mem = defaultdict(int)
for _ in range(N) :
    a, b = map(int, input().split())
    for i in range(max(1, a-1), min(H, a+1)+1) :
        for j in range(max(1, b-1), min(W, b+1)+1) :
            mem[(i, j)] += 1
            
ret = [0] * 10
for k, v in mem.items() :
    if 2 <= k[0] <= H - 1 and 2 <= k[1] <= W - 1 :
        ret[v] += 1

ret[0] = (H - 2) * (W - 2) - sum(ret)
 
for r in ret :
    print(r)

Submission status: Accepted

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    h,w,n=map(int,input().split())
    d={}
    t=[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]
    for i in range(n):
        y,x=map(int,input().split())
        for a,b in t:
            a+=y
            b+=x
            if 0<a<=h and 0<b<=w and (a,b) in d: d[(a,b)]+=1
            elif 0<a<=h and 0<b<=w: d[(a,b)]=1

    ans=[0]*10
    for i in d:
        if i[0]>2 and i[1]>2:
            ans[d[i]]+=1

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

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    h,w,n=map(int,input().split())
    d={}
    for i in range(n):
        y,x=map(int,input().split())
        if (y,x) in d:
            d[(y,x)]+=1
        else:
            d[(y,x)]=1
        if y+1<=h and (y+1,x) in d:
            d[(y+1,x)]+=1
        elif y+1<=h:
            d[(y+1,x)]=1
        if y+2<=h and (y+2,x) in d:
            d[(y+2,x)]+=1
        elif y+2<=h:
            d[(y+2,x)]=1
 
        if x+1<=w and (y,x+1) in d:
            d[(y,x+1)]+=1
        elif x+1<=w:
            d[(y,x+1)]=1
        if x+2<=w and (y,x+2) in d:
            d[(y,x+2)]+=1
        elif x+2<=w:
            d[(y,x+2)]=1
        if x+1<=w and y+1<=h and (y+1,x+1) in d:
            d[(y+1,x+1)]+=1
        elif x+1<=w and y+1<=h:
            d[(y+1,x+1)]=1
        if x+2<=w and y+1<=h and (y+1,x+2) in d:
            d[(y+1,x+2)]+=1
        elif x+2<=w and y+1<=h:
            d[(y+1,x+2)]=1
        if x+1<=w and y+2<=h and (y+2,x+1) in d:
            d[(y+2,x+1)]+=1
        elif x+1<=w and y+2<=h:
            d[(y+2,x+1)]=1
        if x+2<=w and y+2<=h and (y+2,x+2) in d:
            d[(y+2,x+2)]+=1
        elif x+2<=w and y+2<=h:
            d[(y+2,x+2)]=1
    ans=[0]*10
    for i in d:
        if i[0]>2 and i[1]>2:
            ans[d[i]]+=1
 
    ans[0]=h*w-sum(ans)-w*2-h*2+4
    for i in ans:
        print(i)
        
if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

H, W, N = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hist = set()

count = defaultdict(int)
for dx, dy in itertools.product([0, 1, 2], repeat=2):
    for a, b in AB:
        count[(a + dx, b + dy)] += 1
ans = [0] * 10
for [a, b], cnt in count.items():
    if 3 <= a <= H and 3 <= b <= W:
        ans[cnt] += 1
print((H - 2) * (W - 2) - sum(ans[1:]))
print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

H, W, N = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hist = set()

count = defaultdict(int)
for a, b in AB:
    for dx, dy in itertools.product([0, 1, 2], repeat=2):
        count[(a + dx, b + dy)] += 1
ans = [0] * 10
for [a, b], cnt in count.items():
    if 3 <= a <= H and 3 <= b <= W:
        ans[cnt] += 1
print((H - 2) * (W - 2) - sum(ans[1:]))
print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict
H,W,N = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]

d = defaultdict(lambda:0)
def count(a,b):
    for dx1 in [-1,0,1]:
        for dy1 in [-1,0,1]:
            x,y = a+dx1,b+dy1
            if 2<=x<H and 2<=y<W:
                d[(x,y)] += 1

for i in range(N):
    count(*ab[i])

ans = defaultdict(lambda:0)
for x,y in d:
    ans[d[(x,y)]] += 1

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

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

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
dic={}
dx=[-2,-1,0]
dy=[-2,-1,0]
ans=[0]*10
for _ in range(n):
  a,b=map(int,input().split())
  for x in dx:
    for y in dy:
      if 1<=a+y and a+y+2<=h and 1<=b+x and b+x+2<=w:
        if (a+y,b+x) not in dic:
          dic[(a+y,b+x)]=1
        else:
          dic[(a+y,b+x)]+=1
ans[0]=(h-2)*(w-2)-len(dic)
for v in dic.values():
  ans[v]+=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
L = defaultdict(int)

#黒く塗りつぶしたマスとその周りだけ探索すればよい
for i in range(N):
    a,b = map(int,input().split())
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] += 1
            
ans = [0]*10
for v in L.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:
H,W,N = map(int,input().split())

from collections import defaultdict
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] += 1
            
ans = [0]*10
for v in L.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:
H,W,N = map(int,input().split())

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] += 1
ans = [0]*10
for v in L.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, Counter
import sys
import itertools
input = sys.stdin.readline

c = defaultdict(int)
H,W,N = map(int,input().split())
for _ in range(N):
  a,b = map(int,input().split())
  # そのセルを含む正方形の中心を記録
  for dx,dy in itertools.product([-1,0,1],repeat = 2):
    aa = a + dx
    bb = b + dy
    if 2 <= aa <= H-1 and 2 <= bb <= W-1:
	    c[(aa,bb)] += 1

result = Counter(c.values())
result[0] = (H-2)*(W-2) - sum(result.values())

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

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)

h,w,n = map(int, input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())
    a[i] -= 1; b[i] -= 1
    
## 左上のマスを(0,0)とする
## 正方形の左上のマスを(j,i)とする

for x in range(n):
    for k in range(3):
        for l in range(3):
            i = a[x]-k ; j = b[x]-l
            if i<0 or i+3>h or j<0 or j+3>w:
                continue
            d[(j,i)] += 1

ans =[0]*10
for k,v in d.items():
    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
d = defaultdict(int)

h,w,n = map(int, input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())
    a[i] -= 1; b[i] -= 1
    
## 左上のマスを(0,0)とする
## 正方形の左上のマスを(j,i)とする
sq_i = []
sq_j = []

for x in range(n):
    for k in range(3):
        for l in range(3):
            i = a[x]-k ; j = b[x]-l
            if i<0 or i+3>h or j<0 or j+3>w:
                continue
            d[(j,i)] += 1

ans =[0]*10
for k,v in d.items():
    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
H, W, N = map( int, input().split())
D = defaultdict( int)
def check(t):
    a, b = t
    if a == 0 or a == H-1:
        return False
    if b == 0 or b == W-1:
        return False
    return True
for _ in range(N):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    if a >= 1:
        if b >= 1:
            D[(a-1,b-1)] += 1
        if b < W-1:
            D[(a-1,b+1)] += 1
        D[(a-1,b)] += 1
    if a < H-1:
        if b >= 1:
            D[(a+1,b-1)] += 1
        if b < W-1:
            D[(a+1,b+1)] += 1
        D[(a+1,b)] += 1
    if b >= 1:
        D[(a,b-1)] += 1
    if b < W-1:
        D[(a,b+1)] += 1
    D[(a,b)] += 1
ANS = [0]*10
for c in D:
    if check(c):
        ANS[D[c]] += 1
ANS[0] = (H-2)*(W-2)- sum(ANS)
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
d = (-1,0,1)
cmap = ddict(int)
h,w,n = map(int, input().split())
for _ in range(n):
  a,b = map(int, input().split()) 
  for x in d:
    for y in d:
      ca = a+x
      cb = b+y
      if 1<ca<h and 1<cb<w:
        cmap[(ca,cb)] += 1
l = [0]*10
j = list(cmap.values())
for i in range(1,10):
  l[i] = j.count(i)
l[0] = (h-2)*(w-2) - sum(l)
for x in l:
  print(x)

Submission status: Accepted

Solution code:
from collections import defaultdict

H,W,N=map(int,input().split())
ab=[]
dict=defaultdict(int)
for i in range(N):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    for x in [-1,0,1]:
        for y in [-1,0,1]:
            Y=a+y
            X=b+x
            if 0<=Y-1 and Y+1<H and 0<=X-1 and X+1<W:
                dict[(X,Y)]+=1
M=H*W-2*W-2*H+4
v=[0]*10
for i,j in dict.items():
    v[j]+=1
v[0]=M-sum(v[1:])
for i in range(10):
    print(v[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

h, w, n = map(int, input().split())
d = defaultdict(int)
for i in range(n):
    a, b = map(int, input().split())
    for k in range(max(1, a - 2), min(h - 2, a) + 1):
        for l in range(max(1, b - 2), min(w - 2, b) + 1):
            x = (k, l)
            d[x] += 1
ans = [0] * 10
for v in d.values():
    ans[v] += 1
ans[0] = (h - 2) * (w - 2) - sum(ans[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)
for i in range(n):
    a, b = map(int, input().split())
    for k in range(3):
        if 1 <= a - k <= h - 2:
            for l in range(3):
                if 1 <= b - l <= w - 2:
                    x = (a - k, b - l)
                    d[x] += 1
ans = [0] * 10
for v in d.values():
    ans[v] += 1
ans[0] = (h - 2) * (w - 2) - sum(ans[1:])
for i in range(10):
    print(ans[i])

Submission status: Accepted

Solution code:
H,W,N = [ int(it) for it in input().split() ]

di = set()

for i in range(N):
  di.add( tuple( int(it) for it in input().split() ) )

po = set()
for a,b in di:
  for da in [-1,0,1]:
    for db in [-1,0,1]:
      if (1<=a+da and a+da<=H and 1<=b+db and b+db<=W):
        po.add( (a+da,b+db) )

li = [0]*10
for a,b in po:
  k = 0
  if ( a == 1 or a == H or b == 1 or b == W ):
    continue
  for da in [-1,0,1]:
    for db in [-1,0,1]:
      if ( (a+da,b+db) in di ):
        k+=1
  li[k]+=1
li[0] += (H-2)*(W-2) - sum(li)      
      
for i in range(10):
  print ( li[i] )

Submission status: Accepted

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

c = Counter()
H,W,N = map(int,input().split())
for _ in range(N):
  a,b = map(int,input().split())
  # そのセルを含む正方形の中心を記録
  for dx,dy in itertools.product([-1,0,1],repeat = 2):
    aa = a + dx
    bb = b + dy
    if 2 <= aa <= H-1 and 2 <= bb <= W-1:
	    c[(aa,bb)] += 1

result = Counter(c.values())
result[0] = (H-2)*(W-2) - sum(result.values())

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

Submission status: Accepted

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


D = defaultdict(int)
for i in range(N):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1
    for dh in range(-1, 2):
        for dw in range(-1, 2):
            if not ((1 <= h + dh < H - 1) and (1 <= w + dw < W - 1)):
                continue
            D[(h + dh, w + dw)] += 1

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

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

Submission status: Accepted

Solution code:
import collections as cl
h,w,n = map(int,input().split())
l = []
for i in range(n):
  a,b = map(int,input().split())
  for i in range(3):
    x = a+(i-1)
    if x in [0,1,h,h+1]:
      continue
    for j in range(3):
      y = b+(j-1)
      if y in [0,1,w,w+1]:
        continue
      l.append((x-1)*w+y)
#print(l)
p = cl.Counter(l)
q = cl.Counter(p.values())
print((h-2)*(w-2)-sum(q.values()))
for i in range(1,10):
  if i in q.keys():
    print(q[i])
  else:print(0)

Submission status: Accepted

Solution code:
import collections as cl
h,w,n = map(int,input().split())
l = []
for i in range(n):
  a,b = map(int,input().split())
  for i in range(3):
    x = a+(i-1)
    if x in [-1,0,1,h,h+1,h+2]:
      continue
    for j in range(3):
      y = b+(j-1)
      if y in [-1,0,1,w,w+1,w+2]:
        continue
      l.append((x-1)*w+y)
#print(l)
p = cl.Counter(l)
q = cl.Counter(p.values())
print((h-2)*(w-2)-sum(q.values()))
for i in range(1,10):
  if i in q.keys():
    print(q[i])
  else:print(0)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
ans = 0
tmp = 0
inf = 10 ** 20
INF = float("INF")
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
ddn9 = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

h, w, n = wi()
c = mip(n)

d = collections.defaultdict(int)

for i in range(n):
    for dx, dy in ddn9:
        nx = c[i][1] + dx;
        ny = c[i][0] + dy
        if 0 < nx < w - 1 and 0 < ny < h - 1:
            d[str(ny) + "+" + str(nx)] += 1#前のままだと，28+1,2+81とかがが被る

ansli = [0] * 10
for i in d:
    ansli[d[i]] += 1

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

Submission status: Accepted

Solution code:
H,W,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*N]
d={}
for a,b in ab:
    for i in (a-1,a,a+1):
        for j in (b-1,b,b+1):
            d[(i,j)] = d.get((i,j),0)+1
cnt = [0]*10
for k,v in d.items():
    a,b = k
    if a<2 or b<2:continue
    if a>H-1 or b>W-1:continue
    cnt[v] += 1
cnt[0] = (W-2)*(H-2)-sum(cnt)
for ans in cnt:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_input():
    h, w, n = map(int, input().split())
    alist = []
    for i in range(n):
        (px, py) = map(int, input().split())
        alist.append((px, py))

    return h, w, n, alist


def count_arround(px, py, count):
    for xx in [-2, -1, 0]:
        for yy in [-2, -1, 0]:
            count[(px+xx, py+yy)] += 1


def is_area(p, h, w):
    if 1 <= p[0] <= h - 2:
        if 1 <= p[1] <= w - 2:
            return True
    return False


def submit():
    h, w, n, alist = read_input()

    count = defaultdict(int)

    for a in alist:
        count_arround(a[0], a[1], count)

    counts = count.items()
    counts = [c[1] for c in counts if is_area(c[0], h, w)]

    result = []
    s = 0
    for i in range(1, 10):
        result.append(sum([1 for c in counts if c == i]))
        s += result[-1]

    print((h - 2)*(w - 2) - s)
    for r in result:
        print(r)


if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
from collections import Counter
q=[]
h,w,n=map(int,input().split())
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            if (x-2+j)<1 or (x-2+j)>h-2 or (y-2+k)<1 or (y-2+k)>w-2:
                0
            else:
                q.append((x-2+j,y-2+k))
c=Counter(q)
ans=[0]*10
while c:
    ans[c.popitem()[1]]+=1
ans[0]=(h-2)*(w-2)-sum(ans[1:])
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
	H, W, N = map(int, input().split())
	offset = [[i, j] for i in range(-1, 2) for j in range(-1, 2)]
	ans = [0]*10
	ans[0] = (H-2)*(W-2)
	memo = defaultdict(int)
	for i in range(N):
		a, b = map(int, input().split())
		for o in offset:
			if a+o[0] < 2 or H-1 < a+o[0]:
				continue
			if b+o[1] < 2 or W-1 < b+o[1]:
				continue
			memo[(a-1+o[0], b-1+o[1])] += 1
	for v in memo.values():
		ans[v] += 1
		ans[0] -= 1

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


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

from itertools import product

# S = [set() for _ in range(10)]
# S[i]: set(黒いマスをi個こ含む3*3マスの中心セル)

memo = {}
ans = [0]*10

P = list(product([-1,0,1], repeat=2))

for a,b in AB:
  for x,y in P:
    X = a+x-1
    Y = b+y-1
    #print(a,b,x,y,X,Y, ans)
    if X<=0 or H-1<=X or Y<=0 or W-1<=Y:
      continue
    memo[(X,Y)] = memo.get((X,Y),0) + 1
    ans[memo[(X,Y)]] += 1
    ans[memo[(X,Y)]-1] -= 1
    
#print(memo)

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

for n in ans[1:]:
  print(n)

Submission status: Accepted

Solution code:
H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

from itertools import product

S = [set() for _ in range(10)]
# S[i]: set(黒いマスをi個こ含む3*3マスの中心セル)

memo = {}
for a,b in AB:
  for x,y in product([-1,0,1], repeat=2):
    X = a+x-1
    Y = b+y-1
    if X<=0 or H-1<=X or Y<=0 or W-1<=Y:
      continue
    memo[(X,Y)] = memo.get((X,Y),0) + 1

#print(memo)

from collections import Counter
c = Counter(memo.values())
L = [c.get(i,0) for i in range(1,10)]

print((H-2)*(W-2) - sum(L))

for l in L:
  print(l)

Submission status: Accepted

Solution code:
H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

from itertools import product

S = [set() for _ in range(10)]
# S[i]: set(黒いマスをi個こ含む3*3マスの中心セル)

for a,b in AB:
  for x,y in product([-1,0,1], repeat=2):
    X = a+x-1
    Y = b+y-1
    if X<=0 or H-1<=X or Y<=0 or W-1<=Y:
      continue
    for i in range(10):
      if (X, Y) in S[i]:
        S[i].remove((X, Y))
        S[i+1].add((X, Y))
        break
    else:
      S[1].add((X, Y))

L = [len(s) for s in S[1:]]
print((H-2)*(W-2) - sum(L))

for l in L:
  print(l)

Submission status: Accepted

Solution code:
from collections import defaultdict
H,W,N = [int(n) for n in input().split()]
# N = int(input())
dxy = [[0,0],[1,0],[0,1],
[-1,0],[0,-1],[1,1],
[-1,-1], [1,-1], [-1,1]]

effdic = defaultdict(int)
for i in range(N):
    a,b = [int(n)-1 for n in input().split()]
    for d in dxy:
        ta, tb = a+d[0], b+d[1]
        if(1 <= ta < H-1 and 1 <= tb < W-1):
            effdic[(ta,tb)] += 1
print((H-2)*(W-2) - len(effdic))
for i in range(1,10):
    tmp=0
    for v in effdic.values():
        if(v == i):
            tmp+=1
    print(tmp)

Submission status: Accepted

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

for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for j in range(-1, 2):
        for k in range(-1, 2):
            if 1 <= a + j < H - 1 and 1 <= b + k < W - 1:
                A[(a + j, b + k)] += 1
                
print((H - 2) * (W - 2) - len(A))
                
for i in range(1, 10):
    cnt = 0
    for v in A.values():
        if v == i:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def get_rect_pos(a, b):
    pos = []
    for i in range(3):
        for j in range(3):
            pos.append((a-i, b-j))

    return pos


def main():
    input = sys.stdin.readline
    H, W, N = map(int, input().split())
    d = defaultdict(lambda: 0)
    for _ in range(N):
        a, b = map(int, input().split())
        pos = get_rect_pos(a, b)
        for p in pos:
            if p[0] <= 0 or p[0] + 2 > H or p[1] <= 0 or p[1] + 2 > W:
                continue

            d[p] += 1

    ans = [0 for _ in range(10)]
    for key in d.keys():
        i = d[key]
        ans[i] += 1

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

    for i in ans:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def snuke_coloring(H: int, W: int, N: int, queries: list) -> list:
    freq = {}
    for h, w in queries:
        # (h, w) を含む 9 この 3x3 行列に含まれる点の数を
        # 増やす。
        h, w = h-1, w-1
        for dh in range(-1, 1 + 1):
            for dw in range(-1, 1 + 1):
                if h + dh < 1 or H - 1 <= h + dh:
                    continue
                if w + dw < 1 or W - 1 <= w + dw:
                    continue

                freq.setdefault((h + dh, w + dw), 0)
                freq[(h + dh, w + dw)] += 1

    ret = [0] * 10
    # 点が 0 の 3x3 行列は freq に含まれないので、
    # (全ての 3x3 行列) - (点をもつ 3x3 行列) で求める。
    ret[0] = (H-2)*(W-2)
    for v in freq.values():
        ret[0] -= 1
        ret[v] += 1

    return ret


if __name__ == "__main__":
    N = 0
    H, W, N = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(N)]
    ans = snuke_coloring(H, W, N, queries)
    for a in ans:
        print(a)