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: Runtime Error

Solution code:
import sys
def 解()
    iH,iW,iN = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    iMax = (iH - 2) * (iW -2)
    #print (iMax)

    dC={}
    for i in range(10):
        dC[i]=0

    #愚直 無理 つらい
    #for i in range(1,iH -1):
    #   for j in range(1,iW-1):
    #       tmp = 0
    #       for a in aD:
    #           if j<= a[1] <=j+2 and i<= a[0] <= i+2:
    #               tmp +=1
    #       dC[tmp] +=1

    #なんというか、面倒くさくなって解法みても
    #面倒くさがらずやれとしか書いてなくてつらい
    dM = {}
    for a in aD:
        y=a[0]
        x=a[1]
        for aP in [(y-2,x-2),(y-2,x-1),(y-2,x),(y-1,x-2),(y-1,x-1),(y-1,x),(y,x-2),(y,x-1),(y,x)]:
            if 0< aP[0]<iH-1 and 0 < aP[1] < iW-1:
                iP = aP[0]*iW + aP[1]
                if iP in dM: #もう最初から足したったらええんや
                    dM[iP] += 1
                else:
                    dM[iP] = 1
    for i in dM:
        dC[dM[i]]+=1

    iAllBM=0
    for i in range(1,10):
        iAllBM+=dC[i]
    dC[0] = iMax -iAllBM #点のないマス0は引き算で出せる

    for i in range(10):
        print(dC[i])
解()

Submission status: Runtime Error

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] * 9
for k, v in Q.items():
    cnt[v] += 1
cnt[0] = (H - 2) * (W - 2) - len(Q)
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import lil_matrix
from collections import defaultdict
n_rows, n_cols, N = map(int, input().split())
matrix = lil_matrix((n_rows, n_cols), dtype=np.int8)

for i in range(N):
    xi, yi = map(int, input().split())
    matrix[xi-1, yi-1] = 1

ret = [0]*10
for row in range(0, n_rows-2):
    for col in range(0, n_cols-2):
        mat = matrix[row:row+3, col:col+3]
        n_block = np.sum(mat)
        ret[n_black] += 1
for r in ret:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import lil_matrix
from collections import defaultdict
n_rows, n_cols, N = map(int, input().split())
matrix = lil_matrix((n_rows, n_cols), dtype=np.int8)

for i in range(N):
    xi, yi = map(int, input().split())
    matrix[xi-1, yi-1] = 1

def count_black(row, col):
    if row + 2 >= n_rows or col + 2 >= n_cols:
        return -1
    mat = matrix[row:row+3, col:col+3]
    return np.sum(mat)

ret = [0]*10
for row in range(0, n_rows-2):
    for col in range(0, n_cols-2):
        n_black = count_black(row, col)
        ret[n_black] += 1
for r in ret:
    print(r)

Submission status: Runtime Error

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

board = [[0]*(w+1) for i in range(h+1)]

ans = [0] * 10
ans[0] = min(0, (h-2)) * min(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[i][j]] -= 1
        board[i][j] += 1
        ans[board[i][j]] += 1
      except:
        pass

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

Submission status: Runtime Error

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

board = [[0]*(w+1) for i in range(h+1)]

ans = [0] * 10
ans[0] = (h-2) * (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[i][j]] -= 1
        board[i][j] += 1
        ans[board[i][j]] += 1
      except:
        pass

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

Submission status: Runtime Error

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

board = [[0]*(w+1) for i in range(h+1)]

ans = [0] * 9
ans[0] = (h-2) * (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[i][j]] -= 1
        board[i][j] += 1
        ans[board[i][j]] += 1
      except:
        pass

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  int w, h, n;
  cin >> w >> h >> n;
  map<pair<int, int>, int> cnt;
  while (n--) {
    int x, y;
    cin >> x >> y;
    for (int i = x - 3; i < x; i++)
      for (int j = y - 3; j < y; j++)
        if (i >= 0 && j >= 0 && i + 2 < w && j + 2 < h)
          cnt[make_pair(i, j)]++;
  }
  vector<long long> res(10, 0);
  res[0] = (long long) (w - 2) * (h - 2);
  for (auto &it:cnt)
    res[it.second]++, res[0]--;
  for (auto &x:res)
    cout << x << endl;
  return 0;
}

Submission status: Runtime Error

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

A=[ [None for i in range(W+1) ] for j in range(H+1)]
for i in range(N):
	a,b=map(int, raw_input().split())
	A[a][b]=1

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

l=defaultdict(lambda: 0)

for x in range(2,H):
	for y in range(2,W):
		cnt=0
		for i,j in D:
			#print x+i,y+j,A[x+i][y+j]
			if A[x+i][y+j]==1:
				cnt+=1
		l[cnt]+=1


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

Submission status: Runtime Error

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

A=[ [None for i in range(W+1) ] for j in range(H+1)]
for i in range(N):
	a,b=map(int, raw_input().split())
	A[a][b]=1

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

l=defaultdict(lambda: 0)

for x in range(2,H):
	for y in range(2,W):
		cnt=0
		for i,j in D:
			#print x+i,y+j,A[x+i][y+j]
			if A[x+i][y+j]==1:
				cnt+=1
		l[cnt]+=1

print l

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc045/tasks/arc061_b

"""
import sys
from sys import stdin
input = stdin.readline


def solve(H, W, N, points):
    ans = [0] * 10              #  3x3のうちマスがi個だけ黒いパタンの数
    checked = set()

    dx = [-2, -1, 0]
    dy = [-2, -1, 0]

    for x, y in points:
        for xx in dx:
            for yy in dy:
                lbx = x + xx
                lby = y + yy
                if (lbx, lby) not in checked:
                    checked.add((lbx, lby))
                    if 1 <= lbx <= W and lbx+2 <= W and 1 <= lby <= H and lby+2 <= H:
                        res = 0
                        for ddx in [0, 1, 2]:
                            t = points[lbx + ddx]
                            if (lbx + ddx, lby) in t:
                                res += 1
                            if (lbx + ddx, lby + 1) in t:
                                res += 1
                            if (lbx + ddx, lby + 2) in t:
                                res += 1
                        ans[res] += 1

    total = (W-2) * (H-2)         #  3x3の正方形の全パタン
    ans[0] = total - sum(ans[1:]) #  1マスも塗られていないのは、全パタン数-一つでも塗ってあるパタン数
    return ans


def main(args):
    points = dict()

    H, W, N = map(int, input().split())
    for _ in range(N):
        y, x = map(int, input().split())
        points[x].add((x, y))

    ans = solve(H, W, N, points)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
from itertools import product as prod

h, w, n = map(int, input().split())
can = [[0] * w for _ in range(h)]

for _ in range(n):
    ai, bi = map(int, input().split())
    a, b = ai - 1, bi - 1
    can[a][b] = 1

ans = [0] * 10
for i, j in prod(range(h-2), range(w-2)):
    idx = sum(can[i][j:j+3]) + sum(can[i+1][j:j+3]) + sum(can[i+2][j:j+3])
    ans[idx] += 1
    # print(can[i][j:j+3])
    # print(can[i+1][j:j+3])
    # print(can[i+2][j:j+3])
    # print()

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

Submission status: Runtime Error

Solution code:
from itertools import product as prod

h, w, n = map(int, input().split())
can = [[0] * w for _ in range(h)]

for _ in range(n):
    ai, bi = map(int, input().split())
    a, b = ai - 1, bi - 1
    can[a][b] = 1

ans = [0] * 9
for i, j in prod(range(h-2), range(w-2)):
    idx = sum(can[i][j:j+3]) + sum(can[i+1][j:j+3]) + sum(can[i+2][j:j+3])
    ans[idx] += 1
    # print(can[i][j:j+3])
    # print(can[i+1][j:j+3])
    # print(can[i+2][j:j+3])
    # print()

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np

H, W, N = list(map(int,input().split()))
counts = np.zeros(10,dtype=int)
if N == 0:
    counts[0] = (H-2)*(W-2)
    for jdx in range(10):
        print( counts[jdx] )
    quit()
A = [0] * N
B = [0] * N
M = np.zeros((H,W), dtype=int)
for idx in range(N):
    A[idx], B[idx] = list(map(int,input().split()))
    M[A[idx]-1,B[idx]-1] = 1

tmp1 = M[0:H-2].copy()
tmp2 = M[1:H-1].copy()
tmp3 = M[2:H].copy()
M2 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M3 = M2.T.copy()
tmp1 = M3[0:W-2].copy()
tmp2 = M3[1:W-1].copy()
tmp3 = M3[2:W].copy()
M4 = tmp1[0:tmp3.shape[0]] + tmp2[0:tmp3.shape[0]] + tmp3[0:tmp3.shape[0]]
M5 = M4.ravel()
remain = (H-2)*(W-2)
for jdx in range(10):
    M5 = M5[M5>jdx]
    counts[jdx] = remain - M5.size
    remain = M5.size

for jdx in range(10):
    print( counts[jdx] )

Submission status: Runtime Error

Solution code:
def solve():
    H, W, N = list(map(int, input().split()))
    a = []
    for i in range(N):
        a.append(list(map(int, input().split())))

    board = np.zeros((H,W))
    for x in a:
        board[x[0]-1][x[1]-1] = 1
    print(ans)

    count = [0]*10
    for i in range(1:H-1):
        for j in range(1:W-1):
            count(int(np.sum(board[i-1:j-1,i+1:j+1]))) += 1
    for i in range(10):
        print(count[i])

solve()

Submission status: Runtime Error

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

vs = []
for i in range(-1, 2):
	for j in range(-1, 2):
		vs.append((i,j))
cnt = []
for _ in range(n):
	a, b = [int(i) for i in input().split()]
	for v in vs:
		aa = a + v[0]
		bb = b + v[1]
		if 2<=aa<=h-1 and 2<=bb<=w-1:
			cnt.append(aa*h+bb)

cnt = Counter(cnt)


cnt2 = [0] * 10
cnt2[0] = (h-2)*(w-2)
for k in cnt:
	c = cnt[k]
	cnt2[c] += 1
	cnt2[0] -= 1

for i in cnt2:
	print(i)