すぬけ君の塗り絵 / Snuke's Coloring [ARC 061, ABC 045 : D]

問題

http://arc061.contest.atcoder.jp/tasks/arc061_b

H行W列のマスがある。
そのうち、Nマスが黒で、他は白で塗られている。
この時、マスの中に完全に含まれる全ての3*3の連続するマス目の中の黒いマスの個数を数える。
各整数j(0 <= j <= 9)について、黒いマスがj個だったマス目の数をそれぞれ出力せよ。

3 <= H, W <= 10^9
0 <= N <= min(10^5, H*W)

考察

1. H,Wの数が大きすぎるのであてにならない
2. 黒いマスの数がmaxで10^5なのでココを軸に考えていく
3. ある黒いマスがあった時に影響されるのは9マスだけ
4. ということは黒いマスが10^5なら最大9*10^9マスしか黒マスの影響をうけない
5. 他の部分は黒マスの影響なし。つまり、黒いマスが0個になる
6. 黒マス1つ1つにつき、それを計算していって最後にまとめればよいのでは？
7. それで解ける

実装

http://arc061.contest.atcoder.jp/submissions/878994

typedef long long ll;
ll H, W;
int N;
map<ll, int> cnt;
map<int, ll> ans;
//-----------------------------------------------------------------
int main() {
	cin >> H >> W >> N;
 
	rep(i, 0, N) {
		int a, b; scanf("%d %d", &a, &b);
		
		rep(y, max(1, a - 2), min((ll)a, H - 2) + 1) rep(x, max(1, b - 2), min((ll)b, W - 2) + 1){
			cnt[(ll)y * 1000000001LL + (ll)x]++;
		}
	}
 
	for (auto p : cnt) {
		ans[p.second]++;
	}
 
	ll sm = 0;
	rep(i, 1, 10) sm += ans[i];
	ans[0] = (H - 2) * (W - 2) - sm;
 
	rep(i, 0, 10) cout << ans[i] << endl;
}