## Editorial for DMOPC '20 Contest 5 P2 - On The Clock

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Notice that on the left edge of column , the imaginary line is at height , and on the right edge, it is at height . Hence, it fully intersects all the pixels from rows to in column . We can print all of these pixels in per pixel, then repeat this process for all other columns to find every lit pixel. One can show that the total number of lit pixels cannot exceed , so the overall time complexity is .

To avoid rounding errors, you may want to use integer division instead of the floating-point floor/ceiling functions.

**Time complexity:**

## Comments