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: Time Limit Exceeded

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

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


def solve(H, W, N, points, x_lut):
    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 = x_lut[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 = []
    x_lut = defaultdict(set)

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

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


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import defaultdict
input = stdin.readline


def solve(H, W, N, points, x_lut):
    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
                        if (lbx, lby) in x_lut[lbx]:
                            res += 1
                        if (lbx, lby + 1) in x_lut[lbx]:
                            res += 1
                        if (lbx, lby + 2) in x_lut[lbx]:
                            res += 1
                        if (lbx + 1, lby) in x_lut[lbx + 1]:
                            res += 1
                        if (lbx + 1, lby + 1) in x_lut[lbx + 1]:
                            res += 1
                        if (lbx + 1, lby + 2) in x_lut[lbx + 1]:
                            res += 1
                        if (lbx + 2, lby) in x_lut[lbx + 2]:
                            res += 1
                        if (lbx + 2, lby + 1) in x_lut[lbx + 2]:
                            res += 1
                        if (lbx + 2, lby + 2) in x_lut[lbx + 2]:
                            res += 1
                        ans[res] += 1

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


def main(args):
    points = []
    x_lut = defaultdict(set)

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

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


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import defaultdict
input = stdin.readline


def locate_square(x, y, i):
    # x, yが3x3の9マスのそれぞれの位置になった際の3x3領域の左上と右下の座標
    start, end = [[[x, y],   [x+2, y+2]], [[x-1, y],   [x+1, y+2]], [[x-2, y],   [x, y+2]],
                  [[x, y-1], [x+2, y+1]], [[x-1, y-1], [x+1, y+1]], [[x-2, y-1], [x, y+1]],
                  [[x, y-2], [x+2, y]],   [[x-1, y-2], [x+1, y]],   [[x-2, y-2], [x, y]]][i]
    return start, end


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

    for x, y in points:
        for i in range(9):
            [lbx, lby], [ubx, uby] = locate_square(x, y, i)
            if (lbx, lby) not in checked:
                checked.add((lbx, lby))
                if 1 <= lbx <= W and 1 <= ubx <= W and 1 <= lby <= H and 1 <= uby <= H:
                    res = 0
                    if (lbx, lby) in x_lut[lbx]:
                        res += 1
                    if (lbx, lby+1) in x_lut[lbx]:
                        res += 1
                    if (lbx, lby+2) in x_lut[lbx]:
                        res += 1
                    if (lbx+1, lby) in x_lut[lbx+1]:
                        res += 1
                    if (lbx+1, lby+1) in x_lut[lbx+1]:
                        res += 1
                    if (lbx+1, lby+2) in x_lut[lbx+1]:
                        res += 1
                    if (lbx+2, lby) in x_lut[lbx+2]:
                        res += 1
                    if (lbx+2, lby+1) in x_lut[lbx+2]:
                        res += 1
                    if (lbx+2, lby+2) in x_lut[lbx+2]:
                        res += 1
                    # xx = x_lut[lbx] | x_lut[lbx+1] | x_lut[lbx+2]
                    # yy = y_lut[lby] | y_lut[lby+1] | y_lut[lby+2]
                    # res = xx & yy
                    ans[res] += 1

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


def main(args):
    points = []
    x_lut = defaultdict(set)
    y_lut = defaultdict(set)

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

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


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import defaultdict
input = stdin.readline


def locate_square(x, y, i):
    # x, yが3x3の9マスのそれぞれの位置になった際の3x3領域の左上と右下の座標
    start, end = [[[x, y],   [x+2, y+2]], [[x-1, y],   [x+1, y+2]], [[x-2, y],   [x, y+2]],
                  [[x, y-1], [x+2, y+1]], [[x-1, y-1], [x+1, y+1]], [[x-2, y-1], [x, y+1]],
                  [[x, y-2], [x+2, y]],   [[x-1, y-2], [x+1, y]],   [[x-2, y-2], [x, y]]][i]
    return start, end


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

    for x, y in points:
        for i in range(9):
            [lbx, lby], [ubx, uby] = locate_square(x, y, i)
            if (lbx, lby) not in checked:
                checked.add((lbx, lby))

                if 1 <= lbx <= W and 1 <= ubx <= W and 1 <= lby <= H and 1 <= uby <= H:
                    xx = x_lut[lbx] | x_lut[lbx+1] | x_lut[lbx+2]
                    yy = y_lut[lby] | y_lut[lby+1] | y_lut[lby+2]
                    res = xx & yy
                    ans[len(res)] += 1

    #for i in range(2, 10):
    #    ans[i] //= i

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


def main(args):
    points = []
    x_lut = defaultdict(set)
    y_lut = defaultdict(set)

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

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


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import defaultdict
input = stdin.readline


def locate_square(x, y, i):
    # x, yが3x3の9マスのそれぞれの位置になった際の3x3領域の左上と右下の座標
    start, end = [[[x, y],   [x+2, y+2]], [[x-1, y],   [x+1, y+2]], [[x-2, y],   [x, y+2]],
                  [[x, y-1], [x+2, y+1]], [[x-1, y-1], [x+1, y+1]], [[x-2, y-1], [x, y+1]],
                  [[x, y-2], [x+2, y]],   [[x-1, y-2], [x+1, y]],   [[x-2, y-2], [x, y]]][i]
    return start, end


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

    for x, y in points:
        for i in range(9):
            [lbx, lby], [ubx, uby] = locate_square(x, y, i)
            if 1 <= lbx <= W and 1 <= ubx <= W and 1 <= lby <= H and 1 <= uby <= H:
                xx = x_lut[lbx] | x_lut[lbx+1] | x_lut[lbx+2]
                yy = y_lut[lby] | y_lut[lby+1] | y_lut[lby+2]
                res = xx & yy
                ans[len(res)] += 1

    for i in range(2, 10):
        ans[i] //= i

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


def main(args):
    points = []
    x_lut = defaultdict(set)
    y_lut = defaultdict(set)

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

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


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from operator import itemgetter
input = stdin.readline


def locate_square(x, y, i):
    # x, yが3x3の9マスのそれぞれの位置になった際の3x3領域の左上と右下の座標
    start, end = [[[x, y],   [x+2, y+2]], [[x-1, y],   [x+1, y+2]], [[x-2, y],   [x, y+2]],
                  [[x, y-1], [x+2, y+1]], [[x-1, y-1], [x+1, y+1]], [[x-2, y-1], [x, y+1]],
                  [[x, y-2], [x+2, y]],   [[x-1, y-2], [x+1, y]],   [[x-2, y-2], [x, y]]][i]
    return start, end


def count_valid_y(array, lby, uby):
    array.sort(key=itemgetter(1))

    lb = 0
    ub = len(array)

    for _ in range(20):
        mid = (ub + lb) // 2
        if array[mid][1] > uby:
            ub = mid
        elif array[mid][1] < lby:
            lb = mid

    t = array[lb:ub]
    tt = [1 for _, y in t if lby <= y <= uby]
    return len(tt)


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

    for x, y in points:
        for i in range(9):
            [lbx, lby], [ubx, uby] = locate_square(x, y, i)
            if 1 <= lbx <= W and 1 <= ubx <= W and 1 <= lby <= H and 1 <= uby <= H:
                sx = bisect_left(x_points, lbx)
                ex = bisect_right(x_points, ubx)
                t = points[sx:ex]
                res = count_valid_y(t, lby, uby)
                # tt = [1 for _, y in t if lby <= y <= uby]
                # res = len(tt)
                ans[res] += 1

    for i in range(2, 10):
        ans[i] //= i

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


def main(args):
    points = []
    x_points = []
    H, W, N = map(int, input().split())
    for _ in range(N):
        y, x = map(int, input().split())
        points.append([x, y])
        x_points.append(x)
    x_points.sort()
    points.sort()
    ans = solve(H, W, N, points, x_points)
    print(*ans, sep='\n')


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

Submission status: Time Limit Exceeded

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

"""
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
input = stdin.readline


def locate_square(x, y, i):
    start, end = [[[x, y],   [x+2, y+2]], [[x-1, y],   [x+1, y+2]], [[x-2, y],   [x, y+2]],
                  [[x, y-1], [x+2, y+1]], [[x-1, y-1], [x+1, y+1]], [[x-2, y-1], [x, y+1]],
                  [[x, y-2], [x+2, y]],   [[x-1, y-2], [x+1, y]],   [[x-2, y-2], [x, y]]][i]
    return start, end


def solve(H, W, N, points, x_points, y_points):
    ans = [0] * 10

    for x, y in points:
        for i in range(9):
            [lbx, lby], [ubx, uby] = locate_square(x, y, i)
            if 1 <= lbx <= W and 1 <= ubx <= W and 1 <= lby <= H and 1 <= uby <= H:
                sx = bisect_left(x_points, lbx)
                ex = bisect_right(x_points, ubx)
                t = points[sx:ex]
                tt = [1 for x, y in t if lby <= y <= uby]
                res = sum(tt)
                ans[res] += 1


    for i in range(2, 10):
        ans[i] //= i

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


def main(args):
    points = []
    x_points = []
    y_points = []
    H, W, N = map(int, input().split())
    for _ in range(N):
        y, x = map(int, input().split())
        points.append([x, y])
        x_points.append(x)
        y_points.append(y)
    x_points.sort()
    y_points.sort()
    points.sort()
    ans = solve(H, W, N, points, x_points, y_points)
    print(*ans, sep='\n')


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

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = [[0 for i in range(W+2)] for j in range(H+2)]
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: Time Limit Exceeded

Solution code:
import sys
H, W, N = map(int,input().split())
if N ==0:
  print((H-2)*(W-2))
  for i in range(9): print(0)
  sys.exit()
  
blacks = [[0 for i in range(W+2)] for j in range(H+2)]
for i in range(N):
  a, b = map(int,input().split())
  for dx in [-1,0,1]:
    for dy in [-1,0,1]:
      blacks[a+dx][b+dy]+=1

ans =[0 for i in range(10)]
for j in range(2,H):
  for i in range(2,W):
    ans[blacks[j][i]]+=1
for i in range(10): print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,raw_input().split())
black = {}
for i in xrange(n):
    tile = map(int,raw_input().split())
    black[(tile[0]-1,tile[1]-1)] = 1
topleft = {}
res = [0]*10

for p in black.keys():
    y = p[0]
    x = p[1]
    for i in xrange(max(0,x-2),x+1):
        for j in xrange(max(0,y-2),y+1):
            if i+2 < w and j+2 < h:
                if (j,i) not in topleft:
                    topleft[(j,i)] = 1
                    temp = 0
                    for x0 in xrange(3):
                        for y0 in xrange(3):
                            if (j+y0,i+x0) in black:
                                temp += 1
                    res[temp] += 1

temp = sum(res[1:])
res[0] = (h-2)*(w-2)-temp
#print black
for x in res:
    print x

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,raw_input().split())
black = {}
for i in xrange(n):
    tile = map(int,raw_input().split())
    black[(tile[0]-1,tile[1]-1)] = 1
topleft = {}
res = [0]*10

for p in black:
    y = p[0]
    x = p[1]
    for i in xrange(max(0,x-2),x+1):
        for j in xrange(max(0,y-2),y+1):
            if i+2 < w and j+2 < h:
                if (j,i) not in topleft:
                    topleft[(j,i)] = 1
                    temp = 0
                    for x0 in xrange(3):
                        for y0 in xrange(3):
                            if (j+y0,i+x0) in black:
                                temp += 1
                    res[temp] += 1

temp = sum(res[1:])
res[0] = (h-2)*(w-2)-temp
#print black
for x in res:
    print x

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,raw_input().split())
black = set([])
for i in xrange(n):
    tile = map(int,raw_input().split())
    black.add((tile[0]-1,tile[1]-1))
topleft = set([])
res = [0]*10

for p in black:
    y = p[0]
    x = p[1]
    for i in xrange(max(0,x-2),x+1):
        for j in xrange(max(0,y-2),y+1):
            if i+2 < w and j+2 < h:
                if (j,i) not in topleft:
                    topleft.add((j,i))
                    temp = 0
                    for x0 in xrange(3):
                        for y0 in xrange(3):
                            if (j+y0,i+x0) in black:
                                temp += 1
                    res[temp] += 1

temp = sum(res[1:])
res[0] = (h-2)*(w-2)-temp
#print black
for x in res:
    print x

Submission status: Time Limit Exceeded

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
    pos_black_mapping[a, b] = 1
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            na, nb = a+dx, b+dy
            if (0 <= na < H-2) and (0 <= nb < W-2):
                pos_num_mapping[na, nb] = 1

ans = [0 for _ in range(10)]
for a, b in pos_num_mapping.keys():
    cnt = 0
    for dy in range(3):
        for dx in range(3):
            na, nb = a+dx, b+dy
            if (na, nb) in pos_black_mapping:
                cnt += 1
    ans[cnt] += 1
ans[0] = (W-2)*(H-2) - sum(ans[1:])
for v in ans:
    print v

Submission status: Time Limit Exceeded

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
    dx = (1, 0, -1, 0, 1, 1, -1, -1)
    dy = (0, 1, 0, -1, 1, -1, 1, -1)
    bb = []

    for lp in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1

        if in_field(H, W, a, b):
            bb.append((a,b))

        for i in range(len(dx)):
            if in_field(H, W, a+dx[i], b+dy[i]):
                bb.append((a+dx[i], b+dy[i]))

    bb.sort()
    cnt = 0

    for i, box in enumerate(bb):
        if i == 0:
            cnt += 1
            continue
        if box != bb[i-1]:
            nb[cnt] += 1
            cnt = 1
        else:
            cnt += 1

    if cnt > 0:
        nb[cnt] += 1

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

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

def in_field(H, W, a, b):
    return (1 <= a <= H-2) and (1 <= b <= W-2)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

hwn = map(int, raw_input().split())
ab = []
for i in range(0, hwn[2]):
    ab.append((map(int, raw_input().split())))

xy_combination = []
for i in itertools.product([0, 1, -1], repeat=2):
    xy_combination.append(i)

extended_ab = []
for ab_xy in ab:
    for i in xy_combination:
        tempx = ab_xy[0] + i[0]
        tempy = ab_xy[1] + i[1]
        if 0 < tempx <= hwn[0] \
                and 0 < tempy <= hwn[1]:
            extended_ab.append((tempx, tempy))

uniq_ab = list(set(extended_ab))

count_sum = [0] * 10

for counting_ab in uniq_ab:
    if counting_ab[0] != 1 and counting_ab[1] != 1 and counting_ab[0] != hwn[0] and counting_ab[1] != hwn[1]:
        count_sum[extended_ab.count(counting_ab)] += 1

count_sum[0] = (hwn[0] - 2) * (hwn[1] - 2) - sum(count_sum)
for sum in count_sum:
    print sum

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split())
blacks = [[0 for _ in range(w - 2)] for _ in range (h - 2)]
for _ in range(n):
    a, b = map(int, input().split())
    for p in range(max(0, a - 3), min(a, h - 2)):
        for q in range(max(0, b - 3), min(b, w - 2)):
            blacks[p][q] += 1
count = [0 for _ in range(10)]
for k in range(h - 2):
    for l in range(w -2):
        count[blacks[k][l]] += 1
for i in range(10):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split())
blacks = [[0 for _ in range(w - 2)] for _ in range (h - 2)]
for _ in range(n):
    a, b = map(int, input().split())
    for p in range(a - 3, a):
        for q in range(b - 3, b):
            blacks[p][q] += 1
count = [0 for _ in range(10)]
for k in range(h - 2):
    for l in range(w -2):
        count[blacks[k][l]] += 1
for i in range(10):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, input().split())
black = []
for _ in range(n):
    black.append([int(i) for i in input().split()])
count = [0 for _ in range(10)]
for k in range(w - 2):
    for l in range(h - 2):
        thisbox = 0
        for a in range(k,k+3):
            for b in range(l,l+3):
                if [b+1, a+1] in black:
                    thisbox += 1
        count[thisbox] += 1
for i in range(10):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
F=lambda:tuple(int(X)for X in input().split());H,W,N=F();S={F()for _ in[0]*N};T=set();Z=[0]*10
for Y,X in S:
	for A in range(9):
		P=A,B=X-A%3,Y-A//3
		if(0<A<W-1)*(0<B<H-1)*(P not in T):T.add(P);Z[sum((B+C//3,A+C%3)in S for C in range(9))]+=1
Z[0]+=(H-2)*(W-2)-sum(Z);print(*Z,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, raw_input().split())
dot_list = []
for i in range(n):
    parts = list(map(int, raw_input().split()))
    dot_list.append(parts)

board = [[0 for i in range(w)] for j in range(h)]

for i in dot_list:
    board[i[0] - 1][i[1] - 1] = 1

ans_list = [0 for i in range(10)]
for i in range(h - 2):
    for j in range(w - 2):
        sum_1 = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1] + board[i][j + 2] + board[i + 1][j + 2] + board[i + 2][j + 2]
        ans_list[sum_1] += 1
        
for i in ans_list:
    print i

Submission status: Time Limit Exceeded

Solution code:
h, w, n = map(int, raw_input().split())
dot_list = []
for i in range(n):
    parts = list(map(int, raw_input().split()))
    dot_list.append(parts)

board = [[0 for i in range(w)] for j in range(h)]

for i in dot_list:
    board[i[0] - 1][i[1] - 1] = 1

ans_list = [0 for i in range(10)]
for i in range(h - 2):
    for j in range(w - 2):
        sum_1 = 0
        for k in range(i, i + 3):
            for l in range(j, j + 3):
                if board[k][l] == 1:
                    sum_1 += 1
        ans_list[sum_1] += 1
        
for i in ans_list:
    print i

Submission status: Time Limit Exceeded

Solution code:
from array import array
from collections import Counter

h, w, n = map(int, input().split())
b = array('L', [0] * h)

for y, x in (map(int, input().split()) for _ in range(n)):
    b[y - 1] += 1 << (x - 1)

a = [[bin(b[y] & (7 << x)).count('1') for x in range(w - 2)] for y in range(h)]
c = Counter(sum(a[y + i][x] for i in range(3)) for y in range(h - 2) for x in range(w - 2))
for i in range(10):
    print(c[i] if i in c else 0)

Submission status: Time Limit Exceeded

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)
    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):
            rectmap.append([j-1, k-1])
##    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)
rectmap.sort()
while len(rectmap)!=0 :
    c = rectmap.count(rectmap[0])
    del rectmap[:c]
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Time Limit Exceeded

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)
    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):
            rectmap.append([j-1, k-1])
##    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)
rectmap.sort()
rectmap.append([])
while len(rectmap)!=1 :
#    print(rectmap[0])
#    print(rectmap)
    c=0
#    print(rectmap)
    while rectmap[0]==rectmap[1]:
        c+=1
        rectmap.pop(0)
    c+=1
    rectmap.pop(0)
#    print(rectmap)
#    input()
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Time Limit Exceeded

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 = list(map(int, input().split()))
    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)
rectmap.sort()
rectmap.append([])
while len(rectmap)!=1 :
#    print(rectmap[0])
#    print(rectmap)
    c=0
#    print(rectmap)
    while rectmap[0]==rectmap[1]:
        c+=1
        rectmap.pop(0)
    c+=1
    rectmap.pop(0)
#    print(rectmap)
#    input()
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Time Limit Exceeded

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 = list(map(int, input().split()))
    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)
rectmap.sort()
while rectmap!=[] :
#    print(rectmap[0])
#    print(rectmap)
    count[rectmap.count(rectmap[0])]+=1
    count[0]-=1
    del rectmap[:rectmap.count(rectmap[0])]
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Time Limit Exceeded

Solution code:
import math

H, W, N = map(int, input().split())
board = [[0 for i in range(W+4)] for j in range(H+4)]
ab = [0]*N
count = [0]*10
count[0] = (H-2)*(W-2)
#print(board)
for i in range(0,N):
    ab[i] = list(map(int, input().split()))
    a=ab[i][0]
    b=ab[i][1]
    for j in range(a-1, a+2):
        for k in range(b-1, b+2):
            c=0
            if j>1 and j<H and k>1 and k<W:
#                print(j, k)
                for l in range(j, j+3):
                    for m in range(k, k+3):
                            c+=board[l][m]
#            print(c)
                count[c]-=1
                count[c+1]+=1            
    board[a+1][b+1]=1
#    print(count)
#    print(board)
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)

Submission status: Time Limit Exceeded

Solution code:
Blist = {}
chkedSquare = {}
result = {}
#sA,sBを左上にもつ３×３の四角に■が何個あるか
#■は{'a,b',四角の数}であらわされている
def chkAreaCount(sA,sB):
	count = 0
	if str(sA) + ',' + str(sB) not in chkedSquare:
		for i in range(3):
			chkA = sA + i
			for j in range(3):
				chkB = sB + j
				if str(chkA) + ',' + str(chkB) in Blist:
					count = count + 1
					#print('check' + str(chkA) + ':' + str(chkB) + ':' + str(count))
		#print(str(sA) + ':' + str(sB) + ':' + str(count))
		chkedSquare[str(sA) + ',' + str(sB)] = count
		if count in result:
			result[count] = result[count] + 1
		else:
			result[count] = 1
			
def chkOneBlackSquare(a,b):
	#print('PARENT' + str(a) +','+ str(b))
	for i in range(3):
		sA = a - i
		if sA < 1 :
			break
		if sA + 2 > H:
			continue
		for j in range(3):
			sB = b - j
			if sB < 1:
				break
			if sB + 2 > W:
				continue
			#print(str(sA) +','+ str(sB))
			chkAreaCount(sA,sB)
				
	
if __name__ == '__main__':
	H,W,N = map(int,list(input().split())) 
	for i in range(N):
		a,b = map(int,list(input().split())) 
		Blist[str(a) + ',' + str(b)] = 0
	for key in Blist.keys():
		#print(key)
		a,b = key.split(',')
		chkOneBlackSquare(int(a),int(b))
	#for v in chkedSquare.values():
	#	if v in result:
	#		result[v] = result[v] + 1
	#	else:
	#		result[v] = 1
	for i in range(10):
		if i == 0:
			wholeS = (H-2)*(W-2)
			ZeroS = wholeS - len(chkedSquare)
			print(str(ZeroS))
		elif i in result:
			print(str(result[i]))
			#print('')
		else:
			print('0')
			#print('')