AtCoder Beginner Contest 129：D - Lamp
問題
解法
各行・列について障害物がある x, y 座標をソートして配列に持っておく．これを前処理として行っておく．
各マスについて，そのマスから見て上下左右の最も近い障害物の座標は，前処理で求めておいた配列上で二分探索をすることで求めることができる．各マスについてかかる計算量は O(log(H + W)) なので全体で O(HW log(H + W))．
解答
各行・列について障害物がある x, y 座標をソートして配列に持っておく．これを前処理として行っておく．
各マスについて，そのマスから見て上下左右の最も近い障害物の座標は，前処理で求めておいた配列上で二分探索をすることで求めることができる．各マスについてかかる計算量は O(log(H + W)) なので全体で O(HW log(H + W))．