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:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, N, AB):
    c = Counter()

    ij = list(product([-1, 0, 1], repeat=2))
    for a, b in AB:
        for i, j in ij:
            c[(a+i, b+j)] += 1

    ans = Counter()
    for (i, j), v in c.items():
        if 2 <= i < H and 2 <= j < W:
            ans[v] += 1

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


def main():
    H, W, N = read_int_n()
    AB = [read_int_n() for _ in range(N)]

    slv(H, W, N, AB)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Aug  8 22:33:01 2018
ABC045D
@author: maezawa
"""
import collections
h, w, n = list(map(int, input().split()))
areas = []
for i in range(n):
    ai, bi = list(map(int, input().split()))
    ai -= 1
    bi -= 1
    for j in range(3):
        for k in range(3):
            ci = ai + j - 1
            di = bi + k - 1
            if ci>=1 and ci <= h-2 and di>=1 and di <= w-2:
                areas.append(str(ci)+'-'+str(di))
c = collections.Counter(areas)
#print(c.values())
cn = list(c.values())
cn0 = (h-2)*(w-2)-sum([cn.count(i) for i in range(1,10)])
print(cn0)
for i in range(1,10):
    print(cn.count(i))

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
import sys

sdin = sys.stdin.readline

H,W,N = map(int, sdin().split())
AB = []
for i in range(N):
    AB.append(tuple(map(int, sdin().split())))
    
grid_num = (min(H,W)-2)*(max(H,W)-2)
    
AB = [(a-1,b-1) for a,b in AB]

dic = defaultdict(int)

for a,b in AB:
    for h in range(-1,2):
        if a+h < 1 or a+h > H-2:
            continue
        
        for w in range(-1,2):
            if b+w < 1 or b+w > W-2:
                continue
            
            dic[(a+h,b+w)] += 1
            

cnt = Counter(dic.values())

for i in range(10):
    if i==0:
        print(grid_num - sum(cnt.values()))
    elif not i in cnt.keys():
        print(0)
    else:
        print(cnt[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

h, w, n = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n)]

board = defaultdict(int)

for a, b in A:
    for dx, dy in product((-1, 0, 1), repeat=2):
        board[(a+dx, b+dy)] += 1

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

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

for a in ans:
    print(a)

Submission status: Accepted

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

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

c = defaultdict(int)
for _ in range(N):
    a, b = map(int, input().split())
    for dx, dy in product([-1, 0, 1], repeat=2):
        y = a - 2 + dy
        x = b - 2 + dx
        if 0 <= y < H - 2 and 0 <= x < W - 2:
            c[(x, y)] += 1

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

Submission status: Accepted

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

P = []
for i in range(N):
    pa, pb = input().split()
    P.append((int(pa)-1, int(pb)-1))

Q = {}
for pa, pb in P:
    for i in range(3):
        for j in range(3):
            if (pa - i >= 0) and (pb - j >= 0) and (pa - i <= H - 3) and (pb - j <= W - 3):
                if (pa - i, pb - j) in Q:
                    Q[(pa - i, pb - j)] += 1
                else:
                    Q[(pa - i, pb - j)] = 1
cnt = [0] * 10
for k, v in Q.items():
    cnt[v] += 1
cnt[0] = (H - 2) * (W - 2) - len(Q)
for i in range(10):
    print(cnt[i])

Submission status: Accepted

Solution code:
h, w, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

sa = {}
for a,b in ab:
    for i in range(3):
        aa = a + i
        if aa < 3 or h < aa:
            continue
        for j in range(3):
            bb = b + j
            if bb < 3 or w < bb:
                continue
            id = "%d,%d" % (aa, bb)
            sa[id] = sa.get(id, 0) + 1

s = {}
for x in sa.values():
    s[x] = s.setdefault(x, 0) + 1
print((w - 2) * (h - 2) - len(sa.keys()))
for i in range(1, 10):
    print(s.get(i, 0))

Submission status: Accepted

Solution code:
from itertools import product

h, w, n = list(map(int, input().split()))
idxs = {}
ans = [0]*10
for i in range(n):
    a, b = list(map(int, input().split()))
    for a_, b_ in product(range(a-1, a+2), range(b-1, b+2)):
        if a_ <= 1 or b_ <= 1 or a_ >= h or b_ >= w:
            continue

        # print(a_, b_)
        if (a_, b_) not in idxs.keys():
            idxs[(a_, b_)] = 1
        else:
            idxs[(a_, b_)] += 1
        
for keys, item in idxs.items():
    ans[item] += 1
ans[0] = (h-2)*(w-2)-sum(ans[1:])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
Ans = [0] * 10
Ans[0] = (H-2)*(W-2)
from collections import defaultdict
G = defaultdict(int)
for i in range(N):
    a, b = map(int, input().split())
    for j in range(-1, 2):
        for k in range(-1, 2):
            if 1 < a+j < H and 1 < b+k < W:
                G[(a+j, b+k)] += 1
for k, v in G.items():
     if 1 < k[0] < H and 1 < k[1] < W:
        Ans[v] += 1
        Ans[0] -= 1
for a in Ans:
    print(a)

Submission status: Accepted

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

    color_dict = {}
    for i in range(n):
        a, b = map(int, input().split())
        for j in range(a-2, a+1):
            for k in range(b-2, b+1):
                if 1 <= j <= h-2 and 1 <= k <= w-2:
                    color_dict[(j, k)] = color_dict.get((j, k), 0) + 1

    times = [0 for i in range(10)]
    for i in color_dict:
        times[color_dict[i]] += 1

    times[0] = (h-2) * (w-2) - len(color_dict)

    for i in times:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w, n = [int(i) for i in input().split()]
if n == 0:
  a = b = [0] 
else:
  a, b = zip(*
  [[int(i) for i in input().split()] for j in range(n)])

board = { }

ans = [0] * 10
ans[0] = max(0, (h-2)) * max(0, (w-2))

for a, b in zip(a, b):
  for i in range(max(2, a-1), min(h, a+2)):
    for j in range(max(2, b-1), min(w, b+2)):
      try:
        ans[board.get((i, j), 0)] -= 1
        board[(i, j)] = board.get((i, j), 0) + 1
        ans[board[(i, j)]] += 1
      except:
        pass

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

Submission status: Accepted

Solution code:
# 参考url: https://beta.atcoder.jp/contests/abc045/submissions/2365068

from collections import Counter, defaultdict

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

squares = defaultdict(int)
for i in range(N):
    h, w = map(int, input().split())
    for hh in range(3):
        for ww in range(3):
            th, tw = h-hh, w-ww
            # th, twを左上とする3×3の正方形は与えられたグリッドに収まるか
            if 1 <= th <= H-2 and 1 <= tw <= W-2:
                squares[(th, tw)] += 1

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

# 黒マスが0 = 正方形の総数-黒マスが1個以上の正方形
ans[0] = (H-2)*(W-2) - sum(ans)

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

Submission status: Accepted

Solution code:
h,w,n = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
def sq(a,b,h,w):
	A,B,X = [a-2,a-1,a],[b-2,b-1,b],[]
	for i in A:
		for j in B:
			if 1<=i<=h-2 and 1<=j<=w-2: X.append((i,j))
	return X
y,ans = [],[0 for i in range(10)]
for i,j in x: y += sq(i,j,h,w)
from collections import Counter
for (i,j),k in Counter(y).most_common(): ans[k]+=1
ans[0] = (h-2)*(w-2)-sum(ans)
for i in ans: print(i)

Submission status: Accepted

Solution code:
from collections import Counter
H,W,N = map(int,input().split())
Bs = []
for i in range(N):
    x,y = map(int,input().split())
    for xx in range(3):
        for yy in range(3):
            tx,ty = x-xx,y-yy
            if 1<=tx and tx<=H-2 and 1<=ty and ty<=W-2:
                Bs.append((tx,ty))
C = [0]*10
for (x,y),v in Counter(Bs).most_common():
    C[v] += 1
C[0] = (H-2)*(W-2)-sum(C)
for i in range(10):
    print(C[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

XY=[]
ND=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]]

M=defaultdict(int)
for i in range(N):
  a,b=map(int,input().split())
  XY.append([a-1,b-1])
  for c,d in ND:
    if 1 <= a-1+c < H-1 and 1 <= b-1+d < W-1:
      M[(a-1+c,b-1+d)]+=1

dict={1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
cnt=0
for a,b in M.items():
  dict[b]+=1
  cnt+=1
ans=(H-2)*(W-2)-cnt
print(ans)
for i in range(1,10):
  print(dict[i])

Submission status: Accepted

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

d=[-1,0,1]
D=list(itertools.product(d,d))

A=defaultdict(lambda: 0)
for i in range(N):
	a,b=map(int, raw_input().split())
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			A[(cx,cy)]+=1

C=Counter(A.values())


for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(C.values())
	else:
		print C[i]

Submission status: Accepted

Solution code:
H, W, N = map(int, input().split())
D = {}
V = [-1, 0, 1]
ans = [0]*10
ans[0] = (H-2)*(W-2)
for i in range(N):
    a, b = map(int, input().split())
    for da in V:
        if not 2 <= a + da <= H-1:
            continue
        na = a + da
        for db in V:
            if not 2 <= b + db <= W-1:
                continue
            nb = b + db
            cnt = D[na, nb] = D.get((na, nb), 0) + 1
            ans[cnt-1] -= 1
            ans[cnt] += 1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def d_SnukeColoring(H, W, N, A):
    from collections import Counter
    # 要素(p,q)は、(p,q)を左上とする3x3正方形の中に黒マスを1つ含むことを意味する
    # (p,q)が複数回存在した場合は、正方形の中にその回数だけ黒マスを含むことを意味する
    c = []
    for a, b in A:
        a -= 1
        b -= 1
        for k in range(3):
            for l in range(3):
                p = a - k
                q = b - l
                # この2つの条件文を通った場合、3x3正方形が盤の外に出てしまっている
                if p < 0 or p > H - 3:
                    continue
                if q < 0 or q > W - 3:
                    continue
                c.append((p, q))
    # Counter(c).values():(p,q)を左上とする正方形の中に含まれている黒マスの個数
    # これをCounter()に通すと、黒マスをj個含む正方形の個数が得られる
    c = Counter(Counter(c).values())
    c[0] = (H - 2) * (W - 2) - sum(c.values())  # 黒マスがない正方形の個数
    ans = ''
    for i in range(0, 10):
        ans += str(c[i]) + '\n'
    return ans[:-1]

H,W,N=[int(i) for i in input().split()]
A=[[int(i) for i in input().split()] for j in range(N)]
print(d_SnukeColoring(H, W, N, A))

Submission status: Accepted

Solution code:
from collections import defaultdict
w,h,n = map(int,input().split())
board = defaultdict(lambda: 0)
for i in range(n):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    if x > 1:
        if y > 1 :
            board[(x-2,y-2)] += 1
        if y < h-1 and y > 0:
            board[(x-2,y-1)] += 1
        if y < h-2:
            board[(x-2,y)] += 1
    if x < w-1 and x > 0:
        if y > 1 :
            board[(x-1,y-2)] += 1
        if y < h-1 and y > 0:
            board[(x-1,y-1)] += 1
        if y < h-2:
            board[(x-1,y)] += 1
    if x < w-2:
        if y > 1 :
            board[(x,y-2)] += 1
        if y < h-1 and y > 0:
            board[(x,y-1)] += 1
        if y < h-2:
            board[(x,y)] += 1

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

Submission status: Accepted

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

ans=[(H-2)*(W-2)]+[0]*9
blacks=defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2<=a+dx<H and 2<=b+dy<W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, N = map(int,input().split())
  
ans = [(H-2)*(W-2)] + [0]*9
blacks = defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1
        
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, N = map(int,input().split())
  
ans =[(H-2)*(W-2)]+[0]*9
blacks = defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1
        
for i in range(10): print(ans[i])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
ans =[(H-2)*(W-2)]+[0]*9
blacks = defaultdict(int)
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      if 2 <= a+dx <H and 2 <= b+dy <W:
        ans[blacks[(a+dx,b+dy)]]-=1
        ans[blacks[(a+dx,b+dy)]+1]+=1
      blacks[(a+dx,b+dy)]+=1
        
for i in range(10): print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

board = defaultdict(int)
for i in range(n):
    a, b = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    for dx in range(b-1, b+2):
        if dx <= 0 or dx >= w - 1:
            continue
        for dy in range(a-1, a+2):
            if dy <= 0 or dy >= h - 1:
                continue
            board[(dx, dy)] += 1

for v in board.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


def main():
    H, W, N = map(int, input().split())
    d = defaultdict(int)
    for _ in range(N):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        for y in range(-2, 1):
            for x in range(-2, 1):
                ny, nx = a + y, b + x
                if 0 <= ny < H - 2 and 0 <= nx < W - 2:
                    d[(ny, nx)] += 1
    ans = [0] * 10
    for v in d.values():
        ans[v] += 1
    ans[0] = (H - 2) * (W - 2) - sum(ans)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import Counter

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

squares = defaultdict(lambda: 0)
for i in range(N):
    a,b = map(lambda x: x-1, map(int, raw_input().split()))
    for j in range(max(0,a-2), min(H-2,a+1)):
        for k in range(max(0,b-2), min(W-2,b+1)):
            squares[(j,k)] += 1

counter = Counter(squares.values())
s = sum(counter.values())
print (H-2)*(W-2) - s #not colored
for i in range(1,10):
    print counter[i]

Submission status: Accepted

Solution code:
pos_black_mapping = {}
pos_num_mapping = {}
H, W, N = map(int, raw_input().split())
for i in range(N):
    a, b = map(int, raw_input().split())
    a, b = a-1, b-1
    if (a, b) in pos_black_mapping:
        continue
    pos_black_mapping[a, b] = 1
    for da in range(-1, 2):
        for db in range(-1, 2):
            na, nb = a+da, b+db
            if (0 < na < H-1) and (0 < nb < W-1):
                if not (na, nb) in pos_num_mapping:
                    pos_num_mapping[na, nb] = 0
                pos_num_mapping[na, nb] += 1

ans = [0 for _ in range(10)]
for a, b in pos_num_mapping.keys():
    ans[pos_num_mapping[a, b]] += 1
ans[0] = (W-2)*(H-2) - sum(ans[1:])
for v in ans:
    print v

Submission status: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    H, W, N = map(int, sys.stdin.readline().split())
    nb = [0] * 10
    bm = dict()
    bb = set()

    for lp in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        res = search(H, W, bm, bb, a, b)

        if 1 <= a <= H-2 and 1 <= b <= W-2:
            bm[a,b] = 1 + res
        
        bb.add((a,b))

    # debug(bm, locals())
    for i in bm.values():
        nb[i] += 1

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

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

def search(H, W, bm, bb, a, b):
    res = 0
    dx = (1, 0, -1, 0, 1, 1, -1, -1)
    dy = (0, 1, 0, -1, 1, -1, 1, -1)

    for j in range(8):
        if (a + dx[j], b + dy[j]) in bb:
            res += 1

        if a + dx[j] < 1 or a + dx[j] > H - 2:
            continue
        if b + dy[j] < 1 or b + dy[j] > W - 2:
            continue

        if (a + dx[j], b + dy[j]) not in bm:
            bm[a + dx[j], b + dy[j]] = 0

        bm[a + dx[j], b + dy[j]] += 1

    return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
h, w, n = map(int, input().split())
ab = [[int(i)-1 for i in input().split()] for j in range(n)]

d = defaultdict(int)

for i in range(n):
    for j in range(3):
        for k in range(3):
            if ab[i][0] - j >= 0 and ab[i][1] - k >= 0 and ab[i][0] - j < (h - 2) and ab[i][1] - k < (w - 2):
                d[(ab[i][0]-j, ab[i][1]-k)] += 1

print((h-2)*(w-2)-len(d))

c = Counter(d.values())
for i in range(1, 10):
    print(c[i] if i in c else 0)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

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

for a, b in (map(int, input().split()) for _ in range(n)):
    for y in range(max(0, a - 3), min(a, (h - 2))):
        for x in range(max(0, b - 3), min(b, (w - 2))):
            blacks[(y, x)] += 1

print((h - 2) * (w - 2) - len(blacks))

c = Counter(blacks.values())
for i in range(1, 10):
    print(c[i] if i in c else 0)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

h, w, n = map(int, input().split())
hs, ws = h - 2, w - 2
dd = defaultdict(int)

for a, b in (map(int, input().split()) for _ in range(n)):
    for y in range(max(0, a - 3), min(a, hs)):
        for x in range(max(0, b - 3), min(b, ws)):
            dd[(y, x)] += 1

print(hs * ws - len(dd))

c = Counter(dd.values())
for i in range(1, 10):
    print(c[i] if i in c else 0)

Submission status: Accepted

Solution code:
from itertools import product

H, W, N = 0, 0, 0
filled = {}

def boundary_check(pos):
    """
    (x, y) -> bool
    """
    return pos[0] < W - 2 and pos[1] < H - 2 and pos[0] >= 0 and pos[1] >= 0

def matrix_cell_in(a, b):
    """
    int -> int -> (int, int)

    塗りつぶされたセルの座標から、そのセルが含まれる 3 * 3 連続セルの集合を返す。
    3 * 3 連続セルは左上セルの座標で表現する。
    """
    matrixes = list(product(range(a-2,a+1),(range(b-2, b+1))))
    return list(filter(boundary_check ,matrixes))
    # return matrixes

def fill(pos, cell):
    """
    (int, int) -> unit

    3 * 3連続セルの座標を受け取って、その中の黒マスの数を増やす。まだ塗られていなかった場合は 1 にする。
    """
    if pos in filled:
        filled[pos] += 1
    else:
        filled[pos] = 1


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

for i in range(N):
    b, a = map(int, input().split(" "))
    a, b = a-1, b-1
    for cell in matrix_cell_in(a,b):
        fill(cell, (a,b))

results = [0 for _ in range(10)]
for v in filled.values():
    results[v] += 1

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

for r in results:
    print(r)

Submission status: Accepted

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

ans = [0 for _ in xrange(10)]
ans[0] = (H - 2) * (W - 2)

status = {}
for i in xrange(N):
    ab = AB[i]
    for h in xrange(ab[0]-2, ab[0]+1):
        if h < 1 or h+2 > H:
            continue
        for w in xrange(ab[1]-2, ab[1]+1):
            if w < 1 or w+2 > W:
                continue
            status[(h, w)] = status.get((h, w), 0) + 1
            ans[status[(h, w)] - 1] -= 1
            ans[status[(h, w)]] += 1

for a in ans:
    print a

Submission status: Accepted

Solution code:
import bisect
import sys
import math
import itertools
import collections
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

h,w,n=ii()
kuro=[(0,0) for j in range(n)]
for j in range(n):
    kuro[j]=ii()
ans=[0]*10
sq=[]

for x,y in kuro:
    for dx,dy in itertools.product((-1,0,1),(-1,0,1)):
        if 2<=x+dx<=h-1 and 2<=y+dy<=w-1:
            sq.append((x+dx)*w+(y+dy))

cdict=collections.Counter(sq)
for num,cnt in cdict.items():
    ans[cnt]+=1

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    d = defaultdict(int)
    for _ in range(N):
        a, b = map(int, input().split())
        for y in range(-2, 1):
            for x in range(-2, 1):
                n_y, n_x = y + a, x + b
                if 0 < n_y <= H - 2 and 0 < n_x <= W - 2:
                    d[(n_y, n_x)] += 1

    ans = [0] * 10
    for k, v in d.items():
        ans[v] += 1
    ans[0] = (H - 2) * (W - 2) - sum(ans)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap={}

#print(board)
for i in range(0,N):
    a, b = input().split()
    a = int(a)
    b = int(b)
    ab = (a, b)
    al = max(a-1, 2)
    au = min(a+2, H)
    bl = max(b-1, 2)
    bu = min(b+2, W)

    for j in range(al, au):
        for k in range(bl, bu):
            if (j,k) in rectmap:
                rectmap[(j,k)] +=1
            else:
                rectmap[(j,k)] = 1
#            print(rectmap)
##    for j in range(a-1, a+2):
##        for k in range(b-1, b+2):
##            if j>1 and j<H and k>1 and k<W:
##                rectmap.append([j-1, k-1])
#print(rectmap)
for i in rectmap.values():
    count[i]+=1
    count[0]-=1
for c in count:
    print(c)
#print(H,W,N)
#print(ab)

Submission status: Accepted

Solution code:
from collections import defaultdict
if __name__ == '__main__':
    h, w, n = [int(x) for x in input().split()]
    coords = []
    count = defaultdict(int)
    ans = [0 for x in range(10)]
    ans[0] = (h-2) * (w-2)
    adjacent = [(-1, 1), (0, 1), (1, 1), (-1, 0), (0, 0), (1, 0), (-1, -1), (0, -1), (1, -1)]
    for i in range(n):
        y, x = [int(v) for v in input().split()]
        coords.append((x,y))
    for x,y in coords:
        for dx, dy in adjacent:
            new_x = x + dx
            new_y = y + dy
            if 2 <= new_x <= w-1 and 2 <= new_y <= h-1:
                count[(new_x, new_y)] += 1
    for i in count.values():
        ans[i] += 1
        ans[0] -= 1

    for a in ans:
        print(a)

Submission status: Accepted

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

dxy = [(-1, -1), (-1, 0), (-1, 1),
       (0, -1), (0, 0), (0, 1),
       (1, -1), (1, 0), (1, 1)]

count = {}
ans = [0 for x in range(10)]
ans[0] = (H - 2) * (W - 2)

for _ in range(N):
    x, y = [int(x) for x in input().split()]
    for dx, dy in dxy:
        xx = x + dx
        yy = y + dy
        if 2 <= xx <= H - 1 and 2 <= yy <= W - 1:
            if (xx, yy) in count:
                count[(xx, yy)] += 1
            else:
                count[(xx, yy)] = 1

for i in count.values():
    ans[0] -= 1
    ans[i] += 1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    d = defaultdict(lambda: 0)
    h, w, n = reads()
    for _ in range(n):
        a, b = reads()
        for i in range(3):
            for j in range(3):
                d[(a+i-1,b+j-1)] += 1
    r = [0] * 10
    for k in d:
        y, x = k
        if y < 2 or x < 2 or h-1 < y or w-1 < x:
            continue
        if d[k] < 10:
            r[d[k]] += 1
    r[0] = (h - 2)*(w - 2) - sum(r)
    for l in r:
        print(l)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-

from collections import Counter
H, W, N = map(int, input().split())

ddx = [0, 0, 0, 1, 1, 1, -1, -1, -1]
ddy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]

cnt = []
for _ in range(N):
    y, x = map(int, input().split())
    for dx, dy in zip(ddx, ddy):
        yy = y + dy
        xx = x + dx
        if 1<yy<H and 1<xx<W:
            cnt.append(yy * W + xx)
cnt = Counter(cnt)

ans = [0] * 10
ans[0] = (H-2) * (W-2)
for k in cnt:
    c = cnt[k]
    ans[c] += 1
    ans[0] -= 1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys

#sys.stdin = open('input1.txt', 'r')

H, W , N = map(int, raw_input().split())
squares = {}
results = [0 for _ in range(10)]
for _ in range(N):
	h, w = map(int, raw_input().split())
	for x in [(0, 0), (0, -1), (0, -2), (-1, 0), (-1, -1), (-1, -2), (-2, 0), (-2, -1), (-2, -2)]:
		nh, nw = h + x[0], w + x[1]
		if ((nh < 1) or (nw < 1) or (nh + 2 > H) or (nw + 2 > W)):
			pass
		else:
			if (nh, nw) in squares:
				squares[(nh, nw)] += 1
			else:
				squares[(nh, nw)] = 1

for v in squares.values():
	results[v] += 1

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

for x in range(10):
	print str(results[x])

Submission status: Accepted

Solution code:
H, W, N = map(int, raw_input().split())
dx = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
board = {}
 
for i in xrange(N):
    a, b = map(int, raw_input().split())
    for j in xrange(9):
        x, y = a+dx[j], b+dy[j]
        if x <= 1 or x >= H or y <= 1 or y >= W:
            continue
        if (x, y) in board:
            board[(x, y)] += 1
        else:
            board[(x, y)] = 1
ans = [0] * 10
for v in board.values():
    ans[v] += 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, raw_input().split())
lst = {}
for i in range(N):
  a, b = map(int, raw_input().split())
  for x in range(-2, 1):
    if x + a < 1 or H - 2 < x + a:
      continue
    for y in range(-2, 1):
      if y + b < 1 or W - 2 < y + b:
        continue
      xkey = x + a
      ykey = y + b
      if xkey not in lst:
        lst[xkey] = {}
      lst2 = lst[xkey]
      if ykey not in lst2:
        lst[xkey][ykey] = 1
      else:
        lst[xkey][ykey] += 1

answer = [0 for i in range(10)]
count = 0
for l1 in lst.values():
  for l2 in l1.values():
    answer[l2] += 1
    count += 1
answer[0] = (H-2) * (W-2) - count

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

Submission status: Accepted

Solution code:
import collections


def read_nums():
    return map(int, raw_input().split(' '))


H, W, N = read_nums()

vs = []
for i in range(-1, 2):
    for j in range(-1, 2):
        vs.append((i, j))

cnt = []
for i in range(N):
    a, b = read_nums()
    for v in vs:
        i, j = v
        x = a + i
        y = b + j
        if x >= 2 and x <= H-1 and y >= 2 and y <= W-1:
            cnt.append(x * W + y)

cnt = collections.Counter(cnt)
cnt2 = [0] * 10
cnt2[0] = (H - 2) * (W - 2)

for k in cnt:
    cnt2[cnt[k]] += 1
    cnt2[0] -= 1

for c in cnt2:
    print c