Editorial for Signal Flood

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.

Approach

The coordinate values are at most 1000, so there are only 1000 \times 1000 unit squares that can contribute to the answer.

Instead of adding 1 to every square inside every rectangle, use a 2D difference array:

  • add 1 at (x_1, y_1)
  • subtract 1 at (x_2, y_1) and (x_1, y_2)
  • add 1 at (x_2, y_2)

After processing all rectangles, take 2D prefix sums. The prefix value at cell (x, y) is the number of transmitters covering the unit square with lower-left corner (x, y) .

Count how many of those cells have value exactly K.

This runs in O(N + 1000^2) time.

Solution (Python)

from array import array
import sys


COORD_MAX = 1000
SIZE = COORD_MAX + 1

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
n = next(it)
k = next(it)

diff = [array("i", [0]) * SIZE for _ in range(SIZE)]

for _ in range(n):
    x1 = next(it)
    y1 = next(it)
    x2 = next(it)
    y2 = next(it)
    diff[x1][y1] += 1
    diff[x2][y1] -= 1
    diff[x1][y2] -= 1
    diff[x2][y2] += 1

answer = 0
for x in range(SIZE):
    row = diff[x]
    prev_row = diff[x - 1] if x else None
    running = 0
    for y in range(SIZE):
        running += row[y]
        covered = running + (prev_row[y] if prev_row is not None else 0)
        row[y] = covered
        if x < COORD_MAX and y < COORD_MAX and covered == k:
            answer += 1

print(answer)

Comments

There are no comments at the moment.