Since Santa Claus moves in parallel to the axes, it seems to be sufficient to manage houses on each of such lines.

Let \(\mathrm{Ypos}_x\) be the order set of \(y\) coordinates of the houses whose \(x\) coordinates are \(x\);
let \(\mathrm{Ypos}_x\) be the order set of \(x\) coordinates of the houses whose \(y\) coordinates are \(y\).
For example, for Sample Input 1 we have
\(\mathrm{Ypos}_2=\{1,2\},\mathrm{Ypos}_3=\{3\}\),
\(\mathrm{Xpos}_1=\{2\},\mathrm{Xpos}_2=\{2\},\mathrm{Xpos}_3=\{3\}\).

When Santa Claus travels from \((X,Y)\) to \((X,Y+C)\), he passes through houses corresponding to the elements between \(Y\) and \(Y+C\) of \(\mathrm{Ypos_X}\). This can be enumerated in \(O(\text{the number of such elements}*\log N)\). Same applies to the moves to the other directions. By destroying the houses passed through (by removing them from the set), the entire process can be done in \(O(N\log N)\) time.

writer’s solution (C++)
writer’s solution (Python)