ARC061 - D
D - すぬけ君の塗り絵 / Snuke's Coloring
H, W がクソデカいので全探索はまず無理
N が現実的な大きさなのでそこで何とかできそう
(a, b) が黒く塗られたとき影響の出る 3*3 領域は，
左上の座標が [a-2, a] × [b-2, b] に含まれる高々 9 箇所．
これを unordered_set にぶちこんでおく．
黒く塗られる座標 (a, b) 自身も long long にパックして
vector に突っ込んでソートしておく．
あとは unordered_set にぶちこんだ各座標を取り出して，
そこを左上とする 3*3 領域に含まれる黒マスの個数を二分探索で求める．
unordered_set の要素が高々 9N で二分探索が O(log N) なので
全体の計算量は O(N log N) になり間に合う．
詳しくはコードで
// 座標を long long にパック #define P(i, j) ((i << 32) + j) #define I(p) (p >> 32) #define J(p) (p & ((1LL << 32) - 1)) int main() { cin.tie(0); ios::sync_with_stdio(false); ll H, W, N; cin >> H >> W >> N; vector<ll> points; // 塗られたマス unordered_set<ll> search; // 調べるべき 3*3 領域の左上座標 REP(_i, N) { ll a, b; cin >> a >> b; a--; b--; // 0-indexed points.push_back(P(a, b)); // (a, b) が塗られたとき影響が出るのは左上が // [a-2, a] * [b-2, b] の 3*3 領域のみ for (ll i = max(0LL, a - 2); i <= min(a, H - 3); i++) for (ll j = max(0LL, b - 2); j <= min(b, W - 3); j++) search.insert(P(i, j)); } sort(all(points)); vector<ll> ans(10, 0); for (const auto& p : search) { ll a = I(p); ll b = J(p); ll black = 0; // [a, a+2] * [b, b+2] に存在する黒マスの個数を二分探索で for (ll i = a; i <= a + 2; i++) { ll pp = P(i, b); black += upper_bound(all(points), pp + 2) - lower_bound(all(points), pp); } ans[black]++; } // 白部分を求めるのを忘れない ll sum = accumulate(all(ans), 0LL); ans[0] = (H - 2) * (W - 2) - sum; for (int i = 0; i < 10; i++) cout << ans[i] << endl; return 0; }
