Editorial for Signal Flood

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 grid stored as nested lists:

• 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)

COORD_MAX = 1000
SIZE = COORD_MAX + 1

n, k = map(int, input().split())

diff = [[0] * SIZE for _ in range(SIZE)]

for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    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)