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:
H,W,N=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(N)]
ab.sort()

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)

ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]


area_n=[0 for i in range(1,10)]  
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  ched_list_min_add=[0,0,0]
  ch_list_min_add=[0,0,0]
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ched_list=[]

    
    for i in range(max(0,r_n-2),r_n+1):
      min_flag=True
      if (ab[i][0][0]==row-2 if i==r_n-2 else True) and (ab[i][0][0]>=row-2 if i==r_n-1 else True):
        for j in range(ched_list_min_add[i-max(0,r_n-2)],len(ab[i]) if i!=r_n else c_n):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ched_list.append(ab[i][j])
            if min_flag:
              ched_list_min_add[i-max(0,r_n-2)]=j
              min_flag=False
            
    ch_list=[]    
    for i in range(r_n,min(r_n+3,len(ab))):
      min_flag=True
      if (ab[i][0][0]==row+2 if i==r_n+2 else True) and (ab[i][0][0] if i==r_n+1 else True):
        for j in range(ch_list_min_add[i-r_n] if i!=r_n else c_n,len(ab[i])):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ch_list.append(ab[i][j])
            if min_flag:
              ch_list_min_add[i-r_n]=j
              min_flag=False
      
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
       
        for ch_box_p_r in range(ch_box_or_r,row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ched_list:
              check_on_off=False
        if check_on_off:
          count=0
          
         
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_list:
                count+=1
                
          area_n[count-1]+=1
          
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  ched_list_min_add=[0,0,0]
  ch_list_min_add=[0,0,0]
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ched_list=[]

    
    for i in range(max(0,r_n-2),r_n+1):
      min_flag=True
      if (ab[i][0][0]==row-2 if i==r_n-2 else True) and (ab[i][0][0]>=row-2 if i==r_n-1 else True):
        for j in range(ched_list_min_add[i-max(0,r_n-2)],len(ab[i]) if i!=r_n else c_n):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ched_list.append(ab[i][j])
            if min_flag:
              ched_list_min_add[i-max(0,r_n-2)]=j
              min_flag=False
            
    ch_list=[]    
    for i in range(r_n,min(r_n+3,len(ab))):
      min_flag=True
      if (ab[i][0][0]==row+2 if i==r_n+2 else True) and (ab[i][0][0] if i==r_n+1 else True):
        for j in range(ch_list_min_add[i-r_n] if i!=r_n else c_n,len(ab[i])):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ch_list.append(ab[i][j])
            if min_flag:
              ch_list_min_add[i-r_n]=j
              min_flag=False
      
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        
        ch_old_ab=ched_list
        #ab[r_n][max(0,c_n-(col-ch_box_or_c)):c_n]\
        #+(ab[r_n-2] if ch_row_min==row-2 and ch_box_or_r==row-2 else [])\
        #+(ab[r_n-1] if ch_row_min<=row-1 and ch_box_or_r<=row-1 else [])
        
        ch_new_ab=ch_list
        #ab[r_n][c_n:c_n+ch_box_or_c-col+2+1]\
        #+(ab[r_n+1] if ch_row_max>=row+1 and ch_box_or_r>=row-1 else [])\
        #+(ab[r_n+2] if ch_row_max==row+2 and ch_box_or_r==row else [])
  
         
        
        for ch_box_p_r in range(ch_box_or_r,row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
         
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ched_list=[]
    
    for i in range(max(0,r_n-2),r_n+1):
      if (ab[i][0][0]==row-2 if i==r_n-2 else True) and (ab[i][0][0]>=row-2 if i==r_n-1 else True):
        for j in range(len(ab[i]) if i!=r_n else c_n):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ched_list.append(ab[i][j])
            
    ch_list=[]    
    for i in range(r_n,min(r_n+3,len(ab))):
      if (ab[i][0][0]==row+2 if i==r_n+2 else True) and (ab[i][0][0] if i==r_n+1 else True):
        for j in range(0 if i!=r_n else c_n,len(ab[i])):
          if ab[i][j][1]>col+2:
            break
          elif ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ch_list.append(ab[i][j])
      
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        
        ch_old_ab=ched_list
        #ab[r_n][max(0,c_n-(col-ch_box_or_c)):c_n]\
        #+(ab[r_n-2] if ch_row_min==row-2 and ch_box_or_r==row-2 else [])\
        #+(ab[r_n-1] if ch_row_min<=row-1 and ch_box_or_r<=row-1 else [])
        
        ch_new_ab=ch_list
        #ab[r_n][c_n:c_n+ch_box_or_c-col+2+1]\
        #+(ab[r_n+1] if ch_row_max>=row+1 and ch_box_or_r>=row-1 else [])\
        #+(ab[r_n+2] if ch_row_max==row+2 and ch_box_or_r==row else [])
  
         
        
        for ch_box_p_r in range(ch_box_or_r,row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
         
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ched_list=[]
    
    for i in range(max(0,r_n-2),r_n+1):
      if ab[i][0][0]>=row-2:
        for j in range(len(ab[i]) if i!=r_n else c_n):
          if ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ched_list.append(ab[i][j])
    ch_list=[]
    
    for i in range(r_n,min(r_n+3,len(ab))):
      if ab[i][0][0]<=row+2:
        for j in range(0 if i!=r_n else c_n,len(ab[i])):
          if ab[i][j][1] in [col+k for k in [-2,-1,0,1,2]]:
            ch_list.append(ab[i][j])
      
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        
        ch_old_ab=ched_list
        #ab[r_n][max(0,c_n-(col-ch_box_or_c)):c_n]\
        #+(ab[r_n-2] if ch_row_min==row-2 and ch_box_or_r==row-2 else [])\
        #+(ab[r_n-1] if ch_row_min<=row-1 and ch_box_or_r<=row-1 else [])
        
        ch_new_ab=ch_list
        #ab[r_n][c_n:c_n+ch_box_or_c-col+2+1]\
        #+(ab[r_n+1] if ch_row_max>=row+1 and ch_box_or_r>=row-1 else [])\
        #+(ab[r_n+2] if ch_row_max==row+2 and ch_box_or_r==row else [])
  
         
        
        for ch_box_p_r in range(ch_box_or_r,row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
         
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  
  ch_row_min=row-2
  if ab[r_n-1][0][0]!=row-2 and ab[r_n-2][0][0]!=row-2:
    ch_row_min=row-1
    if ab[r_n-1][0][0]!=row-1:
      ch_row_min=row
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    

    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        
        ch_old_ab=ab[r_n][max(0,c_n-(col-ch_box_or_c)):c_n]\
        +(ab[r_n-2] if ch_row_min==row-2 and ch_box_or_r==row-2 else [])\
        +(ab[r_n-1] if ch_row_min<=row-1 and ch_box_or_r<=row-1 else [])
         
        
        for ch_box_p_r in range(max(ch_box_or_r,ch_row_min),row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
          ch_new_ab=ab[r_n][c_n:c_n+3]\
          +(ab[r_n+1] if (ab[r_n+1][0][0]==row+1 or ab[r_n+1][0][0]==row+2 if r_n<len(ab)-1 else False) else [])\
          +(ab[r_n+2] if (ab[r_n+2][0][0]==row+2 if r_n<len(ab)-2 else False) else [])
          
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  
  ch_row_min=row-2
  if ab[r_n-1][0][0]!=row-2 and ab[r_n-2][0][0]!=row-2:
    ch_row_min=row-1
    if ab[r_n-1][0][0]!=row-1:
      ch_row_min=row
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ch_old_ab=(ab[r_n-2] if ch_row_min==row-2 else [])\
    +(ab[r_n-1] if ch_row_min<=row-1 else [])\
    +ab[r_n][max(0,c_n-2):c_n]
    
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        
        
        
        for ch_box_p_r in range(max(ch_box_or_r,ch_row_min),row+1):
          for ch_box_p_c in range(ch_box_or_c,(ch_box_or_c+3 if ch_box_p_r!=row else col)):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
          ch_new_ab=ab[r_n][c_n:c_n+3]\
          +(ab[r_n+1] if (ab[r_n+1][0][0]==row+1 or ab[r_n+1][0][0]==row+2 if r_n<len(ab)-1 else False) else [])\
          +(ab[r_n+2] if (ab[r_n+2][0][0]==row+2 if r_n<len(ab)-2 else False) else [])
          
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ch_old_ab=(ab[r_n-2] if (ab[r_n-2][0][0]==row-2 if r_n>=2 else False) else [])\
    +(ab[r_n-1] if (ab[r_n-1][0][0]==row-1 or ab[r_n-1][0][0]==row-2 if r_n>=1 else False) else [])\
    +ab[r_n][max(0,c_n-2):c_n]
    
    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True

        for ch_box_p_r in range(ch_box_or_r,ch_box_or_r+3):
          for ch_box_p_c in range(ch_box_or_c,ch_box_or_c+3):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
          ch_new_ab=ab[r_n][c_n:c_n+3]\
          +(ab[r_n+1] if (ab[r_n+1][0][0]==row+1 or ab[r_n+1][0][0]==row+2 if r_n<len(ab)-1 else False) else [])\
          +(ab[r_n+2] if (ab[r_n+2][0][0]==row+2 if r_n<len(ab)-2 else False) else [])
          
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
H,W,N=map(int,input().split())
ab=sorted([list(map(int,input().split())) for i in range(N)])

area_n=[0 for i in range(1,10)]

r_b=[0]
for i in range(1,N):
  if ab[i][0]!=ab[i-1][0]:
    r_b.append(i)
r_b.append(N)


ab=[ab[r_b[i]:r_b[i+1]] for i in range(len(r_b)-1)]

if N is 0:
  ab=[]
  
for r_n in range(len(ab)):
  row=ab[r_n][0][0]
  for c_n in range(len(ab[r_n])):
    col=ab[r_n][c_n][1]
    
    ch_old_ab=(ab[r_n-2] if (ab[r_n-2][0][0]==row-2 if r_n>=2 else False) else [])\
    +(ab[r_n-1] if (ab[r_n-1][0][0]==row-1 or ab[r_n-1][0][0]==row-2 if r_n>=1 else False) else [])\
    +ab[r_n][max(0,c_n-2):c_n]

    for ch_box_or_r in range(max(1,row-2),min(H-2,row)+1):
      for ch_box_or_c in range(max(1,col-2),min(W-2,col)+1):      
        check_on_off=True
        for ch_box_p_r in range(ch_box_or_r,ch_box_or_r+3):
          for ch_box_p_c in range(ch_box_or_c,ch_box_or_c+3):
            if [ch_box_p_r,ch_box_p_c] in ch_old_ab:
              check_on_off=False
        if check_on_off:
          count=0
          
          ch_new_ab=ab[r_n][c_n:c_n+3]\
          +(ab[r_n+1] if (ab[r_n+1][0][0]==row+1 or ab[r_n+1][0][0]==row+2 if r_n<len(ab)-1 else False) else [])\
          +(ab[r_n+2] if (ab[r_n+2][0][0]==row+2 if r_n<len(ab)-2 else False) else [])
          
          for ch_box_p_r in range(row,ch_box_or_r+3):
            for ch_box_p_c in range(ch_box_or_c if ch_box_p_r!=row else col,ch_box_or_c+3):
              if [ch_box_p_r,ch_box_p_c] in ch_new_ab:
                count+=1
                
          area_n[count-1]+=1
          
area_n=[area_n[n] for n in range(len(area_n))]
print((H-2)*(W-2)-sum(area_n))
for i in range(9):
  print(area_n[i])

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**10)+b for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**10)+b+j-2 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**10)+b+j-2)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d=dict()
for a,b in ab:
    if a not in ab_d.keys():
        ab_d[a]={b}
    else:
        ab_d[a].add(b)

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[[2 for _ in [0]*5] for _ in [0]*5]
    for i in range(5):
        if 0<a+i-2<=h:
            if a+i-2 in ab_d.keys():
                temp_d=ab_d[a+i-2]
            else:
                temp_d=set()
            for j in range(5):
                if 0<b+j-2<=w:
                    if b+j-2 in temp_d:
                        temp[i][j]=1
                    else:
                        temp[i][j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[i+k][j+l] for k in range(3) for l in range(3)]
            if 2 not in cnt:
                ans[sum(cnt)-1].add((a+i-2,b+j-2))
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
d = 10**9+1
L = []
S = set()
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
Map =[[0]*5 for _ in range(5)]
ans = [0]*10
for i in S:
    a, b = i
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j

            if (1<=a1<=H) and (1<=b1<=W):
                if (a1, b1) in S:
                    Map[i+2][j+2] = 1
                else:
                    Map[i+2][j+2] = 0
            else:
                Map[i+2][j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            res = 0
            for k in range(3):
                for l in range(3):
                    res+=Map[i+1+k][j+1+l]
            if res>=0:
                ans[res]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, N = map(int, input().split())
d = 10**9+1
L = []
S = set()
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
Map = np.zeros([5, 5], dtype = 'int')
ans = [0]*10
for i in S:
    a, b = i
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j
            if (1<=a1<=H) and (1<=b1<=W):
                if (a1, b1) in S:
                    Map[i+2, j+2] = 1
                else:
                    Map[i+2, j+2] = 0
            else:
                Map[i+2, j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            k = Map[i+1:i+4, j+1:j+4].sum()
            if k>=0:
                ans[k]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, N = map(int, input().split())
d = 10**9+1
L = []
S = set()
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
Map = np.zeros([5, 5], dtype = 'int')
ans = [0]*10
for i in S:
    a, b = i
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j
            if (1<=a1<=H) and (1<=b1<=W):
                if (a1, b1) in S:
                    Map[i+2][j+2] = 1
                else:
                    Map[i+2][j+2] = 0
            else:
                Map[i+2][j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            k = Map[i+1:i+4, j+1:j+4].sum()
            if k>=0:
                ans[k]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, N = map(int, input().split())
d = 10**9+1
L = []
for _ in range(N):
    a, b = map(int, input().split())
    L.append(a*d+b)
S = set(L)
Map = np.zeros([5, 5], dtype = 'int')
ans = [0]*10
for i in L:
    a, b = i//d, i%d
    for i in range(-2, 3):
        for j in range(-2, 3):
            a1, b1 = a+i, b+j
            if (1<=a1<=H) and (1<=b1<=W):
                if (a1*d+b1) in S:
                    Map[i+2][j+2] = 1
                else:
                    Map[i+2][j+2] = 0
            else:
                Map[i+2][j+2] = -100
    for i in range(-1, 2):
        for j in range(-1, 2):
            k = Map[i+1:i+4, j+1:j+4].sum()
            if k>=0:
                ans[k]+=1
for i in range(1, 10)[::-1]:
    ans[i] //=i
ans[0] = (W-2)*(H-2)-sum(ans)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
H, W, N = map(int, input().split())
square = set()
dot = defaultdict(lambda : 0)
for i in range(N):
    a, b = map(lambda x: int(x)-1, input().split())
    dot[(a, b)] = 1
    for y in range(a-2, a+1):
        for x in range(b-2, b+1):
            if 0 <= y < H-2 and 0 <= x < W-2:
                square.add((y, x))
ans = [0] * 10
for y, x in square:
    c = 0
    for i in range(y, y+3):
        for j in range(x, x+3):
            c += dot[(i, j)]
    ans[c] += 1
ans[0] += ans[0] + (H-2) * (W-2) - len(square)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, N = map(int, input().split())
square = set()
dot = defaultdict(lambda : 0)
for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dot[(a, b)] = 1
    for y in range(a-2, a+1):
        for x in range(b-2, b+1):
            if 0 <= y < H-2 and 0 <= x < W-2:
                square.add((y, x))
ans = [0] * 10
for y, x in square:
    c = 0
    for i in range(y, y+3):
        for j in range(x, x+3):
            c += dot[(i, j)]
    ans[c] += 1
ans[0] += ans[0] + (H-2) * (W-2) - len(square)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
H, W, N = map(int, input().split())
S = set()
toCheck = set()
rs = [0] * 10
for _ in range(N):
    a, b = map(int, input().split())
    S.add((a, b))
    for i in range(3):
        for j in range(3):
            toCheck.add((a - i, b - j))

for a, b in toCheck:
    if a + 2 > H or b + 2 > W or b < 1 or a < 1:
        continue
    cnt = 0
    for i in range(3):
        for j in range(3):
            na, nb = a + i, b + j
            if (na, nb) in S:
                cnt += 1
    rs[cnt] += 1

total = max(0, H - 2) * max(0, W - 2)
rs[0] = total - sum(rs[1:])
for it in rs:
    print(it)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    h,w,n=map(int,input().split())
    d={}
    for i in range(n):
        y,x=map(int,input().split())
        if y in d:
            d[y].add(x)
        else:
            d[y]={x}
    for i in range(1,h+1):
        for j in range(1,w+1):
            pass
    ans=[0]*10
    for i in range(3,h+1):
        for j in range(3,w+1):
            chk=0
            if i in d:
                chk+=0+(j in d[i])+(j-1 in d[i])+(j-2 in d[i])
            if i-1 in d:
                chk+=0+(j in d[i-1])+(j-1 in d[i-1])+(j-2 in d[i-1])
            if i-2 in d:
                chk+=0+(j in d[i-2])+(j-1 in d[i-2])+(j-2 in d[i-2])
            ans[chk]+=1
    for i in ans:
        print(i)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

H, W, N = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hist = set()


def count(h, w):
    ret = 0
    for dh, dw in itertools.product([-1, 0, 1], repeat=2):
        ret += (h + dh, w + dw) in hist
    return ret


def ok(a=1, b=1):
    return 1 < a < H and 1 < b < W


ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for a, b in AB:
    hist.add((a, b))
    for dh, dw in itertools.product([-1, 0, 1], repeat=2):
        if not ok(a + dh, b + dw):
            continue
        c = count(a + dh, b + dw)
        ans[c] += 1
        ans[c - 1] -= 1
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H,W,N = map(int,input().split())
d = defaultdict(lambda:0)
ab = [tuple(map(int,input().split())) for _ in range(N)]
for i in range(N):
    d[ab[i]] = 1

ans = defaultdict(lambda:0)
def count(a,b):
    for dx1 in [-1,0,1]:
        for dy1 in [-1,0,1]:
            x,y = a+dx1,b+dy1
            if 2<=x<H and 2<=y<W:
                n = 0
                for dx2 in [-1,0,1]:
                    for dy2 in [-1,0,1]:
                        n += d[(x+dx2,y+dy2)]
                ans[n] += 1

for i in range(N):
    count(*ab[i])

ans[0] = (H-2)*(W-2)
for i in range(1,10):
    ans[0] -= ans[i]//i
    ans[i] //= i

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] = 1



ans = [0]*10
for k in L.keys():
    a,b = k[0],k[1]
    if a < 1 or b < 1 or a >H-2 or b >W-2:
        continue

    c = 0
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            c +=t[(a+p,b+q)]

    ans[c] += 1

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            L[(a+p-1,b+q-1)] = 1



ans = [0]*10
for k in L.keys():
    a,b = k[0],k[1]
    if a < 1 or b < 1 or a >H-2 or b >W-2:
        continue

    c = 0
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            c +=t[(a+p,b+q)]

    ans[c] += 1

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict, Counter
t =defaultdict(int)

L = {}
for i in range(N):
    a,b = map(int,input().split())
    #t[a-1][b-1] = 1
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p-1 not in L:
                L[a+p-1] = []
            L[a+p-1].append(b+q-1)

ans = [0]*10
for k in L.keys():
    ll = set(L[k])
    for v in ll:
        a,b = k,v
        if a < 1 or b < 1 or a >H-2 or b >W-2:
            continue

        c = 0
        for p in [-1,0,1]:
            for q in [-1,0,1]:
                c +=t[(a+p,b+q)]

        ans[c] += 1

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

Submission status: Time Limit Exceeded

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

blacks = [tuple(map(int,input().split())) for i in range(n)]
blacks.sort()
points = set(blacks)
squares = set()
cnts = [0]*10
def inbound(a,b):
    if a>h or a<=0 or b<=0 or b>w:
        return False
    else:
        return True

dxx = [-2,-1,0]
dyy = [-2,-1,0]

for x,y in blacks:
    for dx in dxx:
        for dy in dyy:
            xx = x + dx
            yy = y + dy
            if inbound(xx,yy) and inbound(xx+2,yy+2) and (xx,yy) not in squares:
                cnt = 0
                for i in range(3):
                    for j in range(3):
                        if (xx+i,yy+j) in points:
                            cnt+=1
                cnts[cnt]+=1
                squares.add((xx,yy))
cnts[0] = (h-2)*(w-2)-sum(cnts)
for c in cnts:
    print(c)