Before reading the editorial, please make sure you've read the problem thoroughly multiple times and tried your best to solve it. Thanks!
Proceed to Editorial
For 10% of the marks, we can add to each possible position in our K x K grid.
Time Complexity: O(NK2)
For 30% of the marks, we can use a difference array to speed up the tint factor updates.
Time Complexity: O(NK)
For 40% of the marks, we can use coordinate compression. This means, we notice that the coordinates between the rectangles are unimportant, since they all have the same tint factor.
Thus, we can get all the important xs and ys and sort them. Then, we only update between the compressed xs and ys.
At the end, note that we need to expand each cell, since it may represent more than 1 square.
Note that there are atmost 2N important xs and ys.
Time Complexity: O(N3)
For the remaining marks, we combine observation 1 and 2. We use a difference array along with coordinate compression.
Time Complexity: O(N2)