CLWALL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Soumik Sarkar
Tester: Subham Das
Editorialist: Soumik Sarkar

DIFFICULTY:

MEDIUM

PREREQUISITES:

None

PROBLEM:

Given a rectangular grid of size N \times M, handle U updates that paint a subrectangle one out of 4 distinct colors. Calculate how many cells of each color exist at the end.

EXPLANATION:

We can use the fact that the final color of a cell is determined by the last update that affected it. Therefore, if the queries are processed in reverse order then the first update that affects a cell determines its color and the cell need not be considered for further updates.

Let’s call a cell active if no update has been applied to it yet. And for each cell (x, y), let R_{x,y} be the y value of the nearest active cell to its right. Similarly we can also have D_{x,y} as the x value of the nearest active cell below (x, y). Initially, all R_{x,y} = y+1 and all D_{x,y} = x+1.

When we get an update (x_1, y_1, x_2, y_2), let’s update each row in [x_1.. x_2] sequentially with something like this

update_row(x, y1, y2, color):
    if y1 > y2:
        return y1
    if (x, y1) is active:
        color_count[color] += 1
        set (x, y1) to inactive
    r = update_row(x, R[x][y1], y2, color)
    R[x][y1] = r
    return R[x][y1]

Any cell that is turned inactive once will be skipped over in all future updates, unless it is the starting point. So complexity should be \mathcal{O}(NM) plus the number of update calls.
But wait… since we are updating each row sequentially, there may be U \times N calls to update_row, which will cause TLE.

Notice that N \times M \le 4 \cdot 10^6. So we choose to perform the updates along the smaller dimension of the update after implementing a similar update_column operation. This way the number of calls to update_row or update_coloumn can be at most U \times \sqrt{4 \cdot 10^6} = U \times 2 \cdot 10^3, which fits nicely within the time limit.

AUTHOR’S SOLUTION:

Author’s solution can be found here.