Official Analysis (C++)

Video Solution

By Abhiraj Mallangi

Note: The video solution might not be the same as other solutions. Code in C++ and Java.

Solution

Explanation

We record for each rectangle its respective corner increments and decrements in an auxiliary two dimensional array.

We use a two dimensional difference array to drop “start” and “stop” markers at the corners of each paint rectangle, rather than coloring every square inside. When you later sweep through the grid with a cumulative sum from left to right and top to bottom, those corner markers automatically spread their increments into every cell inside the rectangle (and cancel out outside it). As you then scan across and down, you continually add up these markers so that every cell inside a rectangle ends up with exactly one extra coat and cells outside stay the same.

Then we run a two dimensional prefix sum over that array to rebuild the actual count of coats of paint in every cell. Finally, we scan the reconstructed grid and count how many cells have exactly the required number of coats.

Implementation

Time Complexity: $\mathcal{O}(Width^2)$

Copy
WIDTH = 1000

barn = [[0 for _ in range(WIDTH + 1)] for _ in range(WIDTH + 1)]
with open("paintbarn.in") as read:
	rect_num, paint_req = [int(i) for i in read.readline().split()]
	for _ in range(rect_num):
		start_x, start_y, end_x, end_y = [int(i) for i in read.readline().split()]
		# Set up the prefix sums array with all the corners of the given rectangle
		barn[start_x][start_y] += 1
		barn[start_x][end_y] -= 1