색칠 공부

시간 제한1초메모리 제한512 MB

요약
거대한 격자에 검은 칸이 최대 10만 개 주어질 때, 각 3x3 부분격자가 검은 칸을 정확히 i개 포함하는 경우의 수를 i=0부터 9까지 구한다.
난이도

보통10점 중 6점

유형
누적 합, 해시맵, 구현, 조합론
정답자
아직 제출이 없습니다

문제

크기가 H×WH \times W인 모눈종이가 있고, 1×11 \times 1 크기의 칸으로 나누어져 있다. 이 중 NN개의 칸은 검정색이고, 나머지 칸은 흰색이다.

3×33 \times 3 크기의 모든 부분 모눈종이에 대해서, 검정색 칸의 개수가 ii개인 것이 몇 개 있는지 구해보자. (0≤i≤90 \le i \le 9)

입력

첫째 줄에 모눈종이의 크기 HH, WW와 검정색 칸의 개수 NN이 주어진다.

둘째 줄부터 NN개의 줄에 검정칸의 위치 rr, cc가 한 줄에 하나씩 주어진다. 같은 칸이 여러 번 주어지는 경우는 없다.

출력

총 10개의 줄에 문제의 정답을 출력한다. i+1i+1번째 줄에 검정색 칸의 개수가 ii개인 부분 모눈종이의 개수를 출력한다. (0≤i≤90 \le i \le 9)

제한

  • 3≤H,W≤1093 \le H, W \le 10^9
  • 0≤N≤min⁡(105,H×W)0 \le N \le \min(10^5, H \times W)
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

예제3

  1. 예제 1

    입력
    4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4
    예상 출력
    0
0
0
2
4
0
0
0
0
0

  2. 예제 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
    예상 출력
    4
26
22
10
2
0
0
0
0
0

  3. 예제 3

    입력
    1000000000 1000000000 0
    예상 출력
    999999996000000004
0
0
0
0
0
0
0
0
0