Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. At first, all cells were painted white.

Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.

Compute the following:

For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

Constraints

3 \leq H \leq 10^9

3 \leq W \leq 10^9

0 \leq N \leq min(10^5,H×W)

1 \leq a_i \leq H (1 \leq i \leq N)

1 \leq b_i \leq W (1 \leq i \leq N)

(a_i, b_i) \neq (a_j, b_j) (i \neq j)

Input

The input is given from Standard Input in the following format:

H W N
a_1 b_1
:
a_N b_N

Output

Print 10 lines.
The (j+1)-th ( 0 \leq j \leq 9 ) line should contain the number of the subrectangles of size 3×3 of the grid that contains exactly j black cells.

Sample Input 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

Sample Output 1

0
0
0
2
4
0
0
0
0
0

There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.

Sample Input 2

10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9

Sample Output 2

4
26
22
10
2
0
0
0
0
0

Sample Input 3

1000000000 1000000000 0

Sample Output 3

999999996000000004
0
0
0
0
0
0
0
0
0



Sample input:
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4


Sample output:
0
0
0
2
4
0
0
0
0
0

Submission status: Accepted

Solution code:
def main():

    S = list(input())
    checklist = [0 for i in range(26)]
    for i in S:
        checklist[ord(i) - ord("a")] += 1
    ans = True

    for i in checklist:
        if i > 1:
            ans = False

    if not ans:
        print(-1)
        return 0
    else:
        ans = False
        for i in range(len(checklist)):
            if checklist[i] == 0:
                for i in S:
                    print(i, end="")
                print(chr(i + ord("a")), end = "")
                print()
                ans = True
                break

        if not ans:
            new_S = []
            for i in S:
                new_S.append(ord(i))

            for i in range(len(new_S) - 1):
                if new_S[i] > new_S[i + 1]:
                    for j in range(i - 1):
                        print(S[j], end = "")
                    print(chr(new_S[i - 1] + 1), end = "")
                    print()
                    ans = True
                    break

            if not ans:
                print(-1)
#main()

def ABC069D():

    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(N):
        for j in range(a[i]):
            ans.append(i + 1)
    printlist = [[0 for i in range(W)] for j in range(H)]
    k = 0
    for i in range(H):
        for j in range(W):
            printlist[i][j] = ans[k]
            k += 1
        if i % 2 != 0:
            printlist[i] = printlist[i][::-1]

    for i in range(H):
        for j in range(W):
            print(printlist[i][j], end = "")
            if j != W:
                print(" ", end = "")
        print()
    print()
#ABC069D()

import math
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def ABC057D():

    N, A, B = map(int, input().split())
    v = list(map(int, input().split()))
    v = sorted(v)[::-1]

    anslist = []
    for i in range(A, B + 1):

        anslist.append([sum(v[0:i]) / i, i, v[i - 1]])
    anslist.sort()
    anslist = anslist[::-1]
    ans = anslist[0][0]
    key = anslist[0][2]
    long = anslist[0][1]
    print(ans)
    for i in range(1, len(anslist)):
        if anslist[i][0] == anslist[i - 1][0]:
            ans = anslist[i][0]
            key = anslist[i][2]
            long = anslist[i][1]
        else:
            break
    #print(anslist)
    #print(ans, key, long)
    cnt = 0
    for i in v:
        if i == key:
            cnt += 1

    c = 0
    for i in v[:long]:
        #print(i)
        if i == key:
            c += 1
    #print(c, long)
    ans = 0
    if c == long:
        for i in range(A,  min(B + 1, cnt + 1)):
            ans += cc(cnt, i)
    else:
        ans = cc(cnt, c)
    #print(anslist)
    #print(cnt, c, long)
    print(ans)
#ABC057D()

def ABC104D():
    S = list(input())
    A_cnt = 0
    B_cnt = 0
    C_cnt = 0
    Q_cnt = 0
    ans = 0
    for i in S:
        if i == "A":
            A_cnt += 1
        elif i == "B":
            B_cnt += 1
        elif i == "C":
            C_cnt += 1
        else:
            Q_cnt += 1
    for i in range(Q_cnt + 1):
        for j in range(Q_cnt - i + 1):
            k = Q_cnt - i - j
            if A_cnt + i > 0 and B_cnt + j > 0 and C_cnt + k > 0:
                f_i = math.factorial(i)
                f_j = math.factorial(j)
                f_k = math.factorial(k)
                if f_i == 0:
                    f_i = 1
                if f_j == 0:
                    f_j = 1
                if f_k == 0:
                    f_k = 1
                ans += (A_cnt + i) * (B_cnt + j) * (C_cnt + k) * math.factorial(Q_cnt) // f_i // f_j // f_k
                print(ans, i, j, k, A_cnt + i, B_cnt + j, C_cnt + k)
                print(math.factorial(Q_cnt), f_i, f_j, f_k)
    print(ans)
#ABC104D()

def ARC082D():
    N = int(input())
    p = list(map(int, input().split()))
    cnt = 0
    if p[N - 1] == N:
        #print(p[N - 1], N)
        p[-2], p[-1] = p[-1], p[-2]
        cnt += 1

    for i in range(N - 1):
        if p[i] == i + 1:
            p[i], p[i + 1] = p[i + 1], p[i]
            cnt += 1
    print(cnt)
#ARC082D()

from queue import Queue
def ABC070D():
    N = int(input())
    a, b, c =map(int, input().split())
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    x = [[] for i in range(N)]
    for i, j in xy:
        x[i - 1].append(j - 1)
        x[j - 1].append(i - 1)

    q = Queue()
    visited = [0 for i in range(N)]

def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    v = list(map(int, input().split()))
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    print(speed_lim)
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 1
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 1, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans)
#ABC076D()

def ABC085D():
    N, H = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    a = []
    b = []
    for i, j in ab:
        a.append(i)
        b.append(j)
    a.sort()
    b.sort()
    a = a[::-1]
    b = b[::-1]
    damage = 0
    cnt = 0
    for i in b:
        if i < a[0]:
            break
        damage += i
        cnt += 1
        if damage >= H:
            break
    key = 0
    if damage < H:
        key = (H - damage) / a[0]
        if int(key) != key:
            key += 1
        key = int(key)

    cnt += key

    print(cnt)
#ABC085D()

def ARC068D():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    count_list = []
    cnt = 1
    #print(A)
    for i in range(1, N):
        if A[i] == A[i - 1]:
            cnt += 1
        else:
            count_list.append(cnt)
            cnt = 1
    count_list.append(cnt)
    ans_cnt = 0
    #print(count_list)
    for i in range(len(count_list)):
        if count_list[i] > 2:
            ans_cnt += (count_list[i] % 2) - 1
            count_list[i] %= 2
            if count_list[i] == 0:
                count_list[i] = 2
    #print(ans_cnt)
    count_list = sorted(count_list)[::-1]
    for i in range(len(count_list) - 1):
        if count_list[i] == 2 and count_list[i + 1] == 2:
            ans_cnt += 1
            count_list[i] = 1
            count_list[i + 1] = 1
    count_list = sorted(count_list)[::-1]
    if count_list[0] == 2:
        count_list[0] = 0
    #print(ans_cnt)
    #print(count_list)
    print(sum(count_list))
#ARC068D()

def ARC073D():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for i in range(N)]
    wv.sort()
    count_list = []
    cnt = 1
    weight_list = []
    s = 0
    g = 0
    for i in range(N - 1):
        if wv[i][0] != wv[i + 1][0]:
            g = i
            count_list.append(cnt)
            weight_list.append([wv[i][0], s, g, cnt])
            s = i + 1
            g = i + 1
            cnt = 1
        else:
            g = i
            cnt += 1

    count_list.append(cnt)
    weight_list.append([wv[-1][0], s, g, cnt])
    print(weight_list)
    wl = []
    for i in weight_list:
        this_weight = i[0]
        this_list = []
        for j in wv[i[1]:i[2] + 1]:
            this_list.append(j[1])
        this_list = sorted(this_list)[::-1]
        print(this_list)
        wl.append([this_weight, this_list])

def ARC081D():
    pattern = []
    N = int(input())
    S1 = list(input())
    S2 = list(input())
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            pattern.append("X")
        else:
            pattern.append("Y")
            i += 1
        i += 1
    ans_list = []
    for i in range(len(pattern)):
        if i == 0:
            if pattern[i] == "X":
                ans_list.append(3)
            else:
                ans_list.append(6)
        else:
            if pattern[i] == "X":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                else:
                    ans_list.append(1)
            elif pattern[i] == "Y":
                if pattern[i - 1] == "X":
                    ans_list.append(2)
                elif pattern[i - 1] == "Y":
                    ans_list.append(3)
    #print(pattern)
    #print(ans_list)
    ans = 1
    for i in ans_list:
        ans *= i
    print(ans % (1000000007))
#ARC081D()

def ARC090D():
    N, M = map(int, input().split())
    LRD = [list(map(int, input().split())) for i in range(M)]
    L = []
    R = []
    D = []
    LRD.sort()
    root = [[] for i in range(N)]
    for i, j, k in LRD:
        L.append(i)
        R.append(j)
        D.append(k)
        root[i - 1].append(j - 1)
    print(root)
#ARC090D()

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)

    #for i in range(N):
     #   for j in range(N):
      #      for k in range(N):
       #         if root[i][j] > root[i][k] + root[k][j]:
        #            root[i][j] = root[i][k] + root[k][j]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[N - i - 1][N - j - 1] > root[N - i - 1][N - k - 1] + root[N - k - 1][N - j - 1]:
                    root[N - i - 1][N - j - 1] = root[N - i - 1][N - k - 1] + root[N - k- 1][N - j - 1]

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
#ABC073D()

def ARC061D():
    H, W, N = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort()
    tmp_list = []
    ans_list = [0 for i in range(10)]
    for x, y, in ab:
        for i in range(x - 3, x):
            for j in range(y - 3, y):
                if 0 <= i < H - 2 and 0 <= j < W - 2:
                    #print(x, y, i, j)
                    tmp_list.append([i, j])
    #print(tmp_list)
    tmp_list.sort()
    temp = 1
    #print(tmp_list)
    cnt = 0
    for i in range(1, len(tmp_list) + 1):
        if i != len(tmp_list):
            if tmp_list[i] == tmp_list[i - 1]:
                temp += 1
            else:
                ans_list[temp] += 1
                temp = 1
                cnt += 1
        else:
            ans_list[temp] += 1
            cnt += 1
    #print(ans_list)

    key = 0
    for i in range(len(ans_list)):
        key += i * ans_list[i]
    ans_list[0] = (H - 2) * (W - 2) - cnt
    #print(key)
    #print((H - 2) * (W - 2) - key)

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

ARC061D()

Submission status: Accepted

Solution code:
def ARC061D():
    H, W, N = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort()
    tmp_list = []
    ans_list = [0 for i in range(10)]
    for x, y, in ab:
        for i in range(x - 3, x):
            for j in range(y - 3, y):
                if 0 <= i < H - 2 and 0 <= j < W - 2:
                    #print(x, y, i, j)
                    tmp_list.append([i, j])
    #print(tmp_list)
    tmp_list.sort()
    temp = 1
    #print(tmp_list)
    cnt = 0
    for i in range(1, len(tmp_list) + 1):
        if i != len(tmp_list):
            if tmp_list[i] == tmp_list[i - 1]:
                temp += 1
            else:
                ans_list[temp] += 1
                temp = 1
                cnt += 1
        else:
            ans_list[temp] += 1
            cnt += 1
    #print(ans_list)

    key = 0
    for i in range(len(ans_list)):
        key += i * ans_list[i]
    ans_list[0] = (H - 2) * (W - 2) - cnt
    #print(key)
    #print((H - 2) * (W - 2) - key)

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

ARC061D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    h, w, n = map(int, input().split())
    ab = []
    for i in range(n):
        a, b = map(int, input().split())
        ab.append((a, b))

    di = {}
    for a, b in ab:
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                x = b + dx
                y = a + dy
                if (2 <= x <= w - 1) and (2 <= y <= h - 1):
                    p = (x, y)
                    if p in di:
                        di[p] += 1
                    else:
                        di[p] = 1

    cnt = [0 for j in range(10)]
    for p in di:
        cnt[di[p]] += 1
    cnt[0] = (h - 2) * (w - 2) - sum(cnt[1:])

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

main()

Submission status: Accepted

Solution code:
from collections import Counter
H, W, N = map(int, input().split())
c = Counter()
for _ in range(N):
    a, b = map(int, input().split())
    for i in range(3):
        for j in range(3):
            if 1 <= a - i <= H - 2 and 1 <= b - j <= W - 2:
                c[a - i, b - j] += 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:
ai_ = lambda: [int(x)-1 for x in input().split()]
ai = lambda: list(map(int, input().split()))

h,w,n = ai()
bl = [ai_() for _ in range(n)]
from collections import defaultdict
d = defaultdict(int)

from itertools import product
l = list(product((-1,0,1), repeat=2))

for a,b in bl:
    for da,db in l:
        if 0 < a+da < h-1 and 0 < b+db < w-1:
            d[(a+da, b+db)] += 1

print((h-2)*(w-2) - len(d))
ll = list(d.values())
for i in range(1, 10):
    print(ll.count(i))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

H, W, N = reads()

field = Counter()
for _ in range(N):
  a, b = reads()
  a, b = a-1, b-1
  for i, j in product(range(-1, 2), range(-1, 2)):
    field[a+i, b+j] += 1

ans = [0] * 10
for (x, y), v in field.items():
  if 1 <= x < H-1 and 1 <= y < W-1:
    ans[v] += 1
ans[0] = (H-2) * (W-2) - sum(ans[1:10])

for a in ans:
  print(a)

Submission status: Accepted

Solution code:
H,W,N=map(int,input().split())
D=dict()
da=[-1,-1,-1,0,0,0,1,1,1]
db=[-1,0,1,-1,0,1,-1,0,1]
for i in range(N):
    a,b=map(int,input().split())
    for j in range(9):
        na=a+da[j]
        nb=b+db[j]
        if 1<na<H and 1<nb<W:
            if (na,nb) in D:
                D[(na,nb)]+=1
            else:
                D[(na,nb)]=1
ans=[0 for i in range(10)]
for i in D:
    ans[D[i]]+=1
tmp=sum(ans)
ans[0]=(H-2)*(W-2)-tmp
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter()

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

ans = [0] * 10

for v in c.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())
dots = [list(map(int, input().split())) for _ in range(n)]

c = Counter()

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

#print(c)
ans = [0] * 10

for v in c.values():
	ans[v] += 1

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

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
from collections import defaultdict, Counter

H, W, N = inpl()
ddic = defaultdict(int)

for _ in range(N):
    A, B = inpl()
    for a in range(max(3, A), min(H, A+2)+1):
        for b in range(max(3, B), min(W, B+2)+1):
            ddic[(a, b)] += 1

C = Counter(ddic.values())

print((H-2)*(W-2) - sum(C.values()))

for i in range(1, 10):
    print(C[i])

Submission status: Accepted

Solution code:
from collections import Counter
h, w, num = map(int, input().split())
lis = []
for i in range(num):
    k, j = map(lambda x: int(x) - 1,input().split())
    for a in range(3):
        for b in range(3):
            cou1 = k - a
            cou2 = j - b 
            if cou1 < 0 or cou1 > h - 3:
                continue
            if cou2 < 0 or cou2 > w - 3:
                continue
            lis.append((cou1, cou2))

lis = Counter(Counter(lis).values())

print((h - 2) * (w - 2) - sum(lis.values()))
for i in range(1, 10):print(lis[i])

Submission status: Accepted

Solution code:
import numpy as np

def snuke_coloring(h, w, poses):
    counts = np.zeros(10, np.int64)
    searched = {}

    for pos in poses:
        for y in range(max(1, pos[0] - 2), min(h - 2, pos[0]) + 1):
            for x in range(max(1, pos[1] - 2), min(w - 2, pos[1]) + 1):
                index = y * w + x
                if index in searched:
                    searched[index] = searched[index] + 1
                else:
                    searched[index] = 1

    for v in searched.values():
        counts[v] += 1

    nonzero_count = int(np.sum(counts))
    counts[0] = (h - 2) * (w - 2) - nonzero_count
    for v in counts: print(v)

h, w, n = map(int, input().split())
poses = [tuple(map(int, input().split())) for _ in range(n)]
snuke_coloring(h, w, poses)

Submission status: Accepted

Solution code:
from collections import Counter
h, w, n = map(int, input().split())
c = []
for k in range(n):
    i, j = map(lambda x: int(x) - 1,input().split())
    for l in range(3):
        for m in range(3):
            p = i - l
            o = j - m 
            if p < 0 or p > h - 3: continue
            if o < 0 or o > w - 3: continue
            c.append((p, o))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

H, W, N = map(int, input().split())
dct = {}
for i in range(N):
    a, b = map(lambda x: int(x) - 1, input().split())
    for x in range(3):
        for y in range(3):
            if 0 <= a - y < H - 2 and 0 <= b - x < W - 2:
                p = (a - y, b - x)
                dct[p] = 1 if (p not in dct) else dct[p] + 1

cnt = [0] * 10
for n in dct.values():
    cnt[n] += 1
cnt[0] = (H - 2) * (W - 2) - len(dct)

for i in cnt:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, N = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in xrange(N)]

d = defaultdict(int)
ans = [0 for _ in range(10)]

for a, b in X:
    for ax in [-1, 0, 1]:
        for bx in [-1, 0, 1]:
            d[(a+ax, b+bx)] += 1
for k in d:
    a, b = k
    if 1 < a < H and 1 < b < W:
        ans[d[k]] += 1

ans0 = (H-2) * (W-2) - sum(ans)
ans[0] = ans0
for x in ans:
    print x

Submission status: Accepted

Solution code:
a=[int(i) for i in input().split()]
b=[]
for i in range(a[2]):
  b.append([int(j) for j in input().split()])
import collections
import time
c=[]
d=[0 for i in range(10)]
for i in range(len(b)):
  for jj in [-2,-1,0]:
    for kk in [-2,-1,0]:
      if 0<b[i][0]+jj<a[0]-1 and 0<b[i][1]+kk<a[1]-1:
       c.append((b[i][0]+jj,b[i][1]+kk))
count_dict = collections.Counter(c)
n=count_dict.values()
for i in n:
  d[i]+=1
d[0]=(a[0]-2)*(a[1]-2)-len(n)
for j in range(10):
 print(d[j])

Submission status: Accepted

Solution code:
H, W, N = map(int, raw_input().split())
D = dict()

for i in range(N):
    a, b = map(int, raw_input().split())
    for a_add in [-1, 0, 1]:
        for b_add in [-1, 0, 1]:
            c = a + a_add
            d = b + b_add
            if c-1 in range(1, H-1) and d-1 in range(1, W-1):
                if D.has_key(str([c, d])):
                    D[str([c, d])] += 1
                else:
                    D[str([c, d])] = 1

res_list = [0]*10
for s in D.keys():
    res_list[D[s]] += 1

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

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

Submission status: Accepted

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

mass_dict = {}

def count_blackmass(y, x):
    # 黒マスの座標を引数として受け取る
    # その黒マスを含んでいる3*3のマスのカウントを1増やす
    # xが列yが行
    global mass_dict
    for i in range(3):
        tmpy = y - i # 黒マスを含んでいる3*3の左上の頂点のy座標
        for j in range(3):
            tmpx = x - j # 黒マスを含んでいる3*3の左上の頂点のx座標
            if 0 < tmpy and 0 < tmpx and tmpx + 2 <= w and tmpy + 2 <= h: #適切な範囲
                if  (tmpx, tmpy) in mass_dict:
                    mass_dict[(tmpx, tmpy)] += 1
                else:
                    mass_dict[(tmpx, tmpy)] = 1


count = [0 for i in range(10)]
for i, j in a_b: # O(N)
    # iが行,jが列を表している
    count_blackmass(i, j)

for val in mass_dict.values():
    count[val] += 1

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

Submission status: Accepted

Solution code:
num_rows, num_cols, n = map(int, raw_input().split())
marks = {}
for i in range(n):
    r, c = map(int, raw_input().split())
    for ri in range(r - 2, r + 1):
        if ri < 1 or ri + 2 > num_rows:
            continue
        for ci in range(c - 2, c + 1): 
            if ci < 1 or ci + 2 > num_cols:
                continue
            k = ri * num_cols + ci
            marks[k] = marks.setdefault(k, 0) + 1
result = 10 * [ 0 ]
result[0] = (num_rows - 2) * (num_cols - 2) - len(marks)
for count in marks.values():
    result[count] += 1
print('\n'.join(map(str, result)))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
from sys import stdin
def gen_b(x,B,b_d):
	if x not in b_d:
		if x < 3: lb = 2
		else: lb = x - 1
		if x > B-2: ub = B-1
		else: ub = x + 1
		b_d[x] = xrange(lb,ub+1)
	return b_d[x]
def solve():
	count = defaultdict(int)
	ans = [0]*10
	xb_d = dict(); yb_d = dict() 
	L = map(lambda x:map(int,x.split()),stdin.readlines())
	H,W,N = L[0]
	for i in xrange(1,N+1):
		for x,y in product(gen_b(L[i][0],H,xb_d),gen_b(L[i][1],W,yb_d)):
			count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] = (H-2)*(W-2) - sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
from sys import stdin
def gen_b(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return xrange(lb,ub+1)
def solve():
	count = defaultdict(int)
	ans = [0]*10
	L = map(lambda x:map(int,x.split()),stdin.readlines())
	H,W,N = L[0]
	for i in xrange(1,N+1):
		for x,y in product(gen_b(L[i][0],H),gen_b(L[i][1],W)):
			count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] = (H-2)*(W-2) - sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	L = map(lambda x:map(int,x.split()),stdin.read().split("\n"))
	H,W,N = L[0]
	for i in xrange(1,N+1):
		xlb,xub = gen_bound(L[i][0],H)
		ylb,yub = gen_bound(L[i][1],W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] = (H-2)*(W-2) - sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	L = map(lambda x:map(int,x.split()),stdin.readlines())
	H,W,N = L[0]
	for i in xrange(1,N+1):
		xlb,xub = gen_bound(L[i][0],H)
		ylb,yub = gen_bound(L[i][1],W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] = (H-2)*(W-2) - sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	L = map(lambda x:map(int,x.split()),stdin.readlines())
	H,W,N = L[0]
	ans[0] = (H-2)*(W-2)
	for i in xrange(1,N+1):
		xlb,xub = gen_bound(L[i][0],H)
		ylb,yub = gen_bound(L[i][1],W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] -= sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	H,W,N = map(int,raw_input().split())
	ans[0] = (H-2)*(W-2)
	for i in xrange(N):
		a,b = map(int,raw_input().split())
		xlb,xub = gen_bound(a,H)
		ylb,yub = gen_bound(b,W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] -= sum(ans[1:])
	for c in ans: print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	H,W,N = map(int,raw_input().split())
	ans[0] = (H-2)*(W-2)
	for i in xrange(N):
		a,b = map(int,raw_input().split())
		xlb,xub = gen_bound(a,H)
		ylb,yub = gen_bound(b,W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				k = x+(y<<34)
				bef_c = count[k]
				ans[bef_c] -= 1
				ans[bef_c+1] += 1
				count[k] += 1
	for c in ans:
		print c
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	H,W,N = map(int,raw_input().split())
	ans[0] = (H-2)*(W-2)
	for i in xrange(N):
		a,b = map(int,raw_input().split())
		xlb,xub = gen_bound(a,H)
		ylb,yub = gen_bound(b,W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				k = (x,y)
				bef_c = count[k]
				count[k] += 1
				ans[bef_c] -= 1
				ans[bef_c+1] += 1
	for c in ans:
		print c
solve()

Submission status: Accepted

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

T = Counter()

for _ in range(N):
    x, y = map(lambda _x: int(_x) - 1, raw_input().split(' '))
    T[(x, y + 1)] += 1
    T[(x, y)] += 1
    T[(x, y - 1)] += 1
    T[(x-1,y+1)] += 1
    T[(x-1,y)] += 1
    T[(x-1,y-1)] += 1
    T[(x + 1, y + 1)] += 1
    T[(x + 1, y)] += 1
    T[(x + 1, y - 1)] += 1

ans = [0] * 10
total_points = H * W - (2 * H) - (2 * (W-2))
positive_points = 0
for (x, y), c in T.iteritems():
    if 0 < x < H-1 and 0 < y < W-1:
        ans[c] += 1
        positive_points += 1
ans[0] = total_points - positive_points

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub
def solve():
	count = defaultdict(int)
	ans = [0]*10
	H,W,N = map(int,raw_input().split())
	ans[0] = (H-2)*(W-2)
	for i in xrange(N):
		a,b = map(int,raw_input().split())
		xlb,xub = gen_bound(a,H)
		ylb,yub = gen_bound(b,W)
		for x in xrange(xlb,xub+1):
			for y in xrange(ylb,yub+1):
				k = (x,y)
				bef_c = count[k]
				count[k] += 1
				ans[bef_c] -= 1
				ans[bef_c+1] += 1
	for c in ans:
		print c
solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10


def f():
    h,w,n = list(map(int, input().split()))
    t = collections.defaultdict(int)
    for _ in range(n):
        a,b = list(map(int, input().split()))
        for i in range(3):
            if a+i < 3 or a+i > h:
                continue
            ai = (a+i) * inf
            for j in range(3):
                if b+j < 3 or b+j > w:
                    continue
                t[ai+b+j] += 1
    r = [0] * 10
    for v  in t.values():
        r[v] += 1
    r[0] = (h-2)*(w-2) - len(t)
    return "\n".join(map(str,r))

print(f())

Submission status: Runtime Error

Solution code:
H,W,N= (int(x) for x in input().split())
a = [0] * N
b = [0] * N
for i in  range(N):
    a[i],b[i] = (int(x) for x in input().split())
black = [[0 for i in range(W)] for j in range(H)]
for i in  range(N):
    black[a[i]-1][b[i]-1] = 1
answer = [0]*9
sum_black = [[0 for i in range(W-2)] for j in range(H-2)]
for i in range (H-2):
    for j in range (W-2):
        sum_black[i][j] = black[i][j] + black[i][j+1] + black[i][j+2] + black[i+1][j] + black[i+1][j+1] + black[i+1][j+2] + black[i+2][j] + black[i+2][j+1] + black[i+2][j+2]
        answer[sum_black[i][j]] += 1
for i in range (9):
    print(answer[i])

Submission status: Runtime Error

Solution code:
h,w,n=map(int,input().split())
p=[]
q=[-1,0,1]
for i in range(n):
    a,b=map(int,input().split())
    for j in q:
        for k in q:
            if 1<=a+j<=h and 1<=b+k<=w:
                p.append([a+j,b+k])
p.sort()
n=len(p)
f=1
ans=[0]*10
p.append([-1,-1])
for i in range(n):
    if p[i]==p[i+1]:
        f+=1
    else:
        ans[f]+=1
s=sum(ans)
ans[0]=(h-2)*(w-2)-s
for i in ans:
    print(i)