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:
def getlist():
	return list(map(int, input().split()))

H, W, N = getlist()
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append([a - j, b - k])

L = sorted(L)
n = len(L)
v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		ans[c] += 1
		c = 1
	v = L[i]
ans[c] += 1

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

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

H, W, N = getlist()
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append([a - j, b - k])

L = sorted(L)
n = len(L)
v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		ans[c] += 1
		c = 1
	v = L[i]
ans[c] += 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
h, w, n = int(sys.stdin.readline().split())

m3x3 =defaultdict(list)
for _ in range(n):
    a, b = int(sys.stdin.readline().split())
    for i in range(max(0, a - 3),min(h - 2, a)):
        for j in range(max(0, b - 3),min(w - 2, b)):
            if (i,j) in  m3x3:
                m3x3[(i,j)] +=1
            else:
                m3x3[(i,j)] =1
v = list(m3x3.values())
k = m3x3.keys()
print((w-2)*(h-2)-len(k))
for j in range(1,10):
    print(v.count(j))

Submission status: Runtime Error

Solution code:
f=lambda:map(int,input().split())
h,w,n=f()
c=[(h-2)*(w-2),*[0]*9]
d={}
while n:
 n-=1;x,y=f()
 for i in range(9):
  a=(x+i%3,y+i//3)
  if h>=x+i%3>2<y+i//3<=w:d[a]=d.get(a,0)+1;c[d[a]-1]-=1;c[d[a]]+=1
print(*c)

Submission status: Runtime Error

Solution code:
H, W, N = map(int, input().split())
mat = [[0]*(W+2) for _ in range(H+2)]

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(-1, 2):
        for j in range(-1, 2):
            mat[a+i][b+j] += 1


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

for a in ans:
    print(a)

Submission status: Runtime Error

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

for _ in range(N):
    a, b = map(int, input().split())
    mat[a-1][b-1] = 1


dp = [[0]*(W-2) for _ in range(H)]
ran = range(W)
for h in range(H):
    for a, b, c in zip(ran, ran[1:], ran[2:]):
        co = mat[h][a]+mat[h][b]+mat[h][c]
        dp[h][a] = co

ans = [0]*10

for h in range(H-2):
    for w in range(W-2):
        tmp = 0
        for i in range(3):
            tmp += dp[h+i][w]
        ans[0] += 1

for a in ans:
    print(a)

Submission status: Runtime Error

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

for _ in range(N):
    a, b = map(int, input().split())
    mat[a-1][b-1] = 1


dp = [[0]*(W-2) for _ in range(H)]
ran = range(W)
for h in range(H):
    for a, b, c in zip(ran, ran[1:], ran[2:]):
        co = mat[h][a]+mat[h][b]+mat[h][c]
        dp[h][a] = co

ans = [0]*10

for h in range(H-2):
    for w in range(W-2):
        tmp = 0
        for i in range(3):
            tmp += dp[h+i][w]
        ans[tmp] += 1

for a in ans:
    print(a)

Submission status: Runtime Error

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

for _ in range(N):
    a, b = map(int, input().split())
    mat[a-1][b-1] = 1


dp = [[0]*W for _ in range(H)]
for h in range(H):
    cnt = 0
    if mat[h][0] == 1:
        dp[h][0] = 1
    for w in range(1, W):
        if mat[h][w] == 1:
            dp[h][w] += 1
        dp[h][w] += dp[h][w-1]


ans = [0]*10
for i in range(10):
    tmp = 0
    for h in range(H-3):
        for w in range(W-3):
            s = 0
            for k in range(3):
                s += dp[h+k][w+2]-dp[h+k][w]
            if s == i:
                tmp += 1
    ans[i] = tmp

for i in ans:
    print(i)

Submission status: Runtime Error

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

for _ in range(N):
    a, b = map(int, input().split())
    mat[a-1][b-1] = 1


dp = [[0]*W for _ in range(H)]
for h in range(H):
    cnt = 0
    if mat[h][0] == 1:
        dp[h][0] = 1
    for w in range(1, W):
        if mat[h][w] == 1:
            dp[h][w] += 1
        dp[h][w] += dp[h][w-1]


ans = [0]*10
for i in range(10):
    tmp = 0
    for h in range(H-3):
        for w in range(w-3):
            s = 0
            for k in range(3):
                s += dp[h+k][w+2]-dp[h+k][w]
            if s == i:
                tmp += 1
    ans[i] = tmp

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int main(void){
    long long h,w,n,d=1000000000,c[10]={0};
    unordered_map<long long,int> m{};
    cin>>h>>w>>n;
    for(int i=0;i<n;i++){
        long long a,b;
        cin>>a>>b;
        a--;
        b--;
        for(int j=-1;j<=1;j++){
            for(int k=-1;k<=1;k++){
                if(a+j>=0&&a+j<h&&b+k>=0&&b+k<w){
                    m[(a+j)*d+b+k]++;
                    //cout<<a+j<<","<<b+k<<":"<<m[(a+j)*d+b+k]<<endl;
                }
            }
        }
        
    }
    for(auto x=m.begin();x!=m.end();x++){
        long long a=(x->first)/d,b=(x->first)%d;
        if(a>=1&&a<=h-2&&b>=1&&b<=w-2){
            c[x->second]++;
            c[0]++;
        }
    }
    cout<<(h-2)*(w-2)-c[0]<<endl;
    for(int i=1;i<=9;i++){
        cout<<c[i]<<endl;
    }
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

map<P, int> mp;
int dy[] = {-2, -2, -2, -1, -1, -1, 0, 0, 0};
int dx[] = {-2, -1, 0, -2, -1, 0, -2, -1, 0};
int ans[10];
signed main(){
	int h, w, n, cnt = 0;
	scanf("%lld%lld%lld", &h, &w, &n);
	rep(i,n){
		int x, y;
		scanf("%lld%lld", &y, &x);
		rep(j,9){
			int yy = y+dy[j];
			int xx = x+dx[j];
			if(yy <= 0 or xx <= 0)continue;
			if(yy+2 > h or xx+2 > w)continue;
			mp[P(yy, xx)]++;
		}
	}
	for(auto it = mp.begin();it != mp.end();it++){
		ans[it->second]++;
		cnt++;
	}
	ans[0] = (h-2)*(w-2)-cnt;
	rep(i,10){
		printf("%lld\n", ans[i]);
	}
	return 0;
}

Submission status: Runtime Error

Solution code:
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 - 1) * w + (x - 1)
                if index in searched: continue
                searched[index] = True

                count = 0
                for target in poses:
                    if x <= target[1] and target[1] <= x + 2 and \
                       y <= target[0] and target[0] <= y + 2:
                       count += 1
                counts[count] += 1

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

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

Submission status: Runtime Error

Solution code:
import sys
grid = []
painted = []

height, width, n = sys.stdin.readline().strip().split()
height, width, n = int(height), int(width), int(n)

def checkGrid(x, y, grid):
    count = 0
    for col in range(x, x+3):
        for row in range(y, y+3):
            if grid[row][col] == 1:
                count += 1
    return count

    # Build empty grid
    for i in range(height):
        painted.append([])
        for j in range(width):
            painted[i].append(0)
    inp = sys.stdin.readline().strip()
    while inp:
        a, b = inp.split()
        grid.append([int(a) - 1, int(b) - 1])
        inp = sys.stdin.readline().strip()

    # Build painted cells
    for cell in grid:
        painted[cell[0]][cell[1]] = 1

for i in range(0, 10):
    count = 0
    for col in range(width - 2):
        for row in range(height - 2):
            if checkGrid(col, row, painted) == i:
                count += 1
    print(count)