Consider one of the sheets and how the area of stained fabric in it changes over time. Analysing various cases we can see that, if ~X~ squares of fabric are initially stained when the oil front hits, then ~X+K~ squares will be stained after a second, ~X+2K~ after two seconds etc. where ~K~ can be zero, two or four. This continues until the entire width or height of the rectangle is stained, after which one additional row or column gets stained per second (we can also recalculate ~X~ at that point and change ~K~ to zero).

One efficient solution calculates the important time points (events), in which ~X~ and ~K~ for a sheet change. The time complexity of this part is ~\mathcal O(N)~. Then we simulate second by second and, using the known data about ~X~ and ~K~ for every rectangle, we can calculate the change of area of stained fabric in ~\mathcal O(1)~ per second.

An alternative approach is to first fold all rectangles into the first quadrant. Then we can represent every rectangle as a combination of four quarter-planes extending up and right (inclusion-exclusion principle) and, similar as before, calculate the change of area of stained fabric in each quarter-plane. Representing rectangles as quarter-planes reduces the number of special cases our implementation needs to handle.