Subtask 1

For this subtask, it is sufficient to build an ~M~ by ~N~ array and mark down each cell that has a block. Then, iterating down each column until a block is reached and adding all empty spaces below that block for each row will earn full marks for this subtask.

Time complexity: ~O(N\times M)~

Subtask 2

For this subtask, simply building an ~M~ by ~N~ array and iterating through it will take too much time and memory. So instead of creating and storing the grid, it should be noticed that the highest block in each column will be the one to block out the rain. Sort the blocks by column, and for each column, the highest block can be found and its height describes the number of cells that it shields from the rain. The remaining blocks that are not blocking the rain (blocks that are under other blocks) must be subtracted off, as they do not count as empty cells.

Alternatively, a map can be used to store the highest block for each column that has at least one block. This avoids creating an array that stores each column by only storing what is needed. Due to map's inconsistent nature, in some languages it may be slower than the previous solution mentioned, but would still be sufficient.

Time complexity: ~O(K\log K)~ or ~O(K)~