サンタクロースは軸に平行な直線上を移動するので、そのような直線上の家をまとめて管理することができればよさそうです。

\(\mathrm{Ypos}_x\) を、\(x\) 座標が \(x\) である家の \(y\) 座標全体のordered set
\(\mathrm{Xpos}_y\) を、\(y\) 座標が \(y\) である家の \(x\) 座標全体のordered set
とします。例えば入力例1に対しては
\(\mathrm{Ypos}_2=\{1,2\},\mathrm{Ypos}_3=\{3\}\)
\(\mathrm{Xpos}_1=\{2\},\mathrm{Xpos}_2=\{2\},\mathrm{Xpos}_3=\{3\}\)
となります。

サンタクロースが \((X,Y)\) から \((X,Y+C)\) \((C>0)\)に移動したときに通過する家は、\(\mathrm{Ypos_X}\) に含まれる \(Y\) 以上 \(Y+C\) 以下の要素になります。これは \(O(そのような要素の個数*\log N)\) で列挙できます。他の方向への移動も同様であり、通過した家は破壊する(集合から取り除く)ことにすると、これらは全体で \(O(N\log N)\) 時間で処理できます。

writer解(C++)
writer解(Python)