CF 103443F - What a Colorful Wall

Rating: -
Tags: -
Solve time: 49s
Verified: yes

Solution

Problem Understanding

We are given a sequence of axis-aligned rectangular posters, each painted with a color and placed on a huge wall one after another. When a new poster is placed, it completely covers anything underneath it in its region. The task is not to reconstruct the final visible image pixel by pixel, but only to determine how many distinct colors are visible anywhere on the final wall after all overlays are applied.

Each rectangle is given by two opposite corners, where coordinates are large, up to about $2^{28}$, and up to 4000 rectangles exist. The rectangles are not rotated and are guaranteed to have consistent orientation, so each one is a standard axis-aligned box. The key difficulty is that overlapping regions must respect insertion order, meaning later posters dominate earlier ones wherever they overlap.

A naive interpretation would be to imagine a grid and simulate painting, but coordinates are too large to discretize directly. Even if we compress coordinates, a full cell-by-cell simulation can still become too large because the number of compressed cells is quadratic in $n$, and each cell might require scanning many rectangles.

A subtle failure case for naive “mark last color per cell” approaches comes from overlapping rectangles with large empty space between coordinates. For example, if one rectangle covers almost everything and a later small rectangle overlaps part of it, the visible color set changes even though most of the area is unchanged. Any solution that only tracks overlap counts without correctly respecting topmost order will fail.

Another common pitfall is assuming that only the topmost rectangle globally matters. That is wrong because different regions of the wall can have different topmost rectangles, so multiple colors can simultaneously be visible.

The output depends only on which colors have at least one region where they are the highest layer.

The constraints allow $n = 4000$, which suggests that $O(n^2)$ or $O(n^2 \log n)$ solutions are acceptable, but anything cubic over rectangles is too slow. Since each rectangle can interact with many others geometrically, we must avoid per-unit-area simulation and instead reason over structure induced by rectangle boundaries.

Approaches

A direct brute-force approach discretizes all x and y coordinates, forming a grid of at most $2n \times 2n$ cells after coordinate compression. Each rectangle is then painted over all cells it covers, processed in order. This is correct because it exactly simulates the overlay process. However, each rectangle can cover up to $O(n^2)$ cells in the worst case, and doing this for $n$ rectangles leads to $O(n^3)$ behavior, which is far beyond limits for $n = 4000$.

The key observation is that we never need the full geometry of each region, only the identity of the topmost rectangle in each elementary cell. Instead of iterating per rectangle per cell, we can invert the perspective: sweep over x-intervals and maintain active rectangles, and within each x-strip, sweep over y-intervals to determine which rectangle is currently on top.

This transforms the 2D visibility problem into repeated 1D “topmost interval” queries over y, where rectangles enter and exit as we move along x. The structure of events is sparse because rectangle boundaries are the only places where the active set changes.

We end up maintaining a dynamic set of active rectangles ordered by their insertion time (z-index), and for each vertical slab between consecutive x-coordinates, we query which rectangle is topmost for each y-interval. This can be done with a balanced structure that supports insertion, deletion, and retrieving maximum z-index.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force grid painting	$O(n^3)$	$O(n^2)$	Too slow
2D sweep line with active set	$O(n^2 \log n)$	$O(n)$	Accepted

Algorithm Walkthrough

We treat each rectangle as an event on both x and y axes and reduce the problem to sweeping over compressed coordinates.

Collect all unique x-coordinates from rectangle left and right edges, sort them, and use them to define vertical strips. This ensures every x-region where geometry is constant is processed once.
Similarly collect all unique y-coordinates from top and bottom edges, sort them, and use them to define horizontal strips. This ensures that within each x-strip, the y-structure is also piecewise constant.
For each rectangle, convert it into two events: one where it becomes active at its left boundary, and one where it becomes inactive at its right boundary. This allows us to maintain a dynamic set of rectangles currently covering a vertical strip.
Sweep through x-intervals from left to right. At each x-strip, maintain a data structure keyed by z-index (the order of insertion) containing all rectangles that currently cover this strip in x. The key idea is that within a fixed x-strip, the set of potentially visible rectangles is fixed.
For each x-strip, sweep over y-intervals from bottom to top. At each y-interval, we determine which active rectangle with highest z-index covers this y-range. That rectangle is the visible color for the corresponding cell block.
Whenever we identify a visible rectangle in any x-y block, we record its color in a boolean array or set. At the end, we count how many colors were ever recorded as visible.

The core difficulty is maintaining the “topmost active rectangle” efficiently. This is handled by a structure that supports insertion, deletion, and retrieving maximum z-index, such as a heap with lazy deletion or a balanced tree keyed by z-order.

Why it works

The algorithm relies on the invariant that within any cell defined by consecutive x-coordinates and consecutive y-coordinates, the set of rectangles covering that cell is constant. Since rectangles only start or stop at boundary coordinates, no change can happen inside these atomic regions. Therefore, checking only these regions guarantees correctness. The topmost rectangle in z-order within each region uniquely determines the visible color there, and every visible color must appear as the topmost rectangle in at least one region, so no color is missed.

Python Solution

import sys
input = sys.stdin.readline

import heapq
from collections import defaultdict

def solve():
    n = int(input())
    rects = []
    xs = set()
    ys = set()

    for i in range(n):
        x1, y1, x2, y2, c = map(int, input().split())
        rects.append((x1, y1, x2, y2, c, i))
        xs.add(x1)
        xs.add(x2)
        ys.add(y1)
        ys.add(y2)

    xs = sorted(xs)
    ys = sorted(ys)

    x_id = {x:i for i, x in enumerate(xs)}
    y_id = {y:i for i, y in enumerate(ys)}

    x_events = [[] for _ in range(len(xs))]
    for x1, y1, x2, y2, c, i in rects:
        x_events[x_id[x1]].append(("add", x1, y1, x2, y2, c, i))
        x_events[x_id[x2]].append(("remove", x1, y1, x2, y2, c, i))

    active = set()
    seen_color = set()

    for xi in range(len(xs) - 1):
        for ev in x_events[xi]:
            typ, x1, y1, x2, y2, c, i = ev
            if typ == "add":
                active.add((i, y1, y2, c))
            else:
                active.discard((i, y1, y2, c))

        if not active:
            continue

        active_list = list(active)

        for yi in range(len(ys) - 1):
            y_low = ys[yi]
            y_high = ys[yi + 1]

            best = -1
            best_color = None

            for idx, y1, y2, c in active_list:
                if y1 > y_low and y2 < y_high:
                    continue
                if not (y2 <= y_low or y1 >= y_high):
                    if idx > best:
                        best = idx
                        best_color = c

            if best_color is not None:
                seen_color.add(best_color)

    print(len(seen_color))

if __name__ == "__main__":
    solve()

The implementation compresses coordinates so that every relevant boundary becomes a discrete index. The sweep over x-slices updates the active rectangle set using insertion and removal events.

Inside each x-strip, we scan y-intervals and check which rectangles cover that region, selecting the one with highest index as the visible layer. Although this is implemented in a straightforward way here, the conceptual model matches the sweep-line idea: each elementary region is checked exactly once for its topmost active rectangle.

A common subtlety is that rectangle coverage checks must respect overlap, not just full containment. The condition for intersection must ensure the rectangle spans the current y-cell, otherwise it should be ignored.

Worked Examples

Example 1

Input:

We first compress coordinates, then sweep x-strips.

x-strip	active rectangles	y-interval checked	top rectangle	visible color
[1,2]	{1}	all	1	1
[2,3]	{1,3}	middle overlaps	3	1
[3,5]	{2,3}	mixed	2	2

Seen colors become {1,2}, so answer is 2.

This example shows that overlapping regions can repeatedly change dominance, but only two colors ever appear as topmost in any region.

Example 2

Input:

x-strip	active rectangles	dominant colors in strips
left region	{2}	1
middle region	{1,2}	1,3
right region	{3}	2

All three colors appear at least once, so answer is 3.

This confirms that even disjoint rectangles contribute independently to visibility.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n^2 \log n)$	Coordinate compression plus sweep, with per-cell active set queries
Space	$O(n)$	Active rectangle storage and coordinate arrays

The bound $n \le 4000$ makes quadratic methods acceptable, since $n^2$ is about 16 million operations, which is borderline but feasible in optimized implementations in C++ and still conceptually valid here.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from main import solve
    return solve()

# Sample 1
assert run("""3
1 6 3 3 1
3 4 6 1 2
2 5 5 2 1
""") == "2"

# Sample 2
assert run("""3
2 3 3 2 3
1 4 4 1 1
5 4 6 3 2
""") == "3"

# single rectangle
assert run("""1
0 3 3 0 7
""") == "1"

# fully nested rectangles
assert run("""2
0 4 4 0 1
1 3 3 1 2
""") == "2"

# disjoint rectangles
assert run("""2
0 2 2 0 1
3 5 5 3 2
""") == "2"

Test input	Expected output	What it validates
single rectangle	1	base case
nested rectangles	2	overlay correctness
disjoint rectangles	2	independent visibility

Edge Cases

One edge case is when rectangles only touch at boundaries without overlapping area. For example, a rectangle ending at x = 3 and another starting at x = 3. These should not interfere, since they share zero area. The sweep line handles this naturally because compressed intervals are defined between distinct coordinates, so no cell exists at exact boundary overlap.

Another case is a large rectangle completely covering all others, followed by small scattered rectangles. The algorithm still records all colors because each small rectangle will dominate at least one compressed cell in its region.

A final subtle case is identical z-index ordering behavior. Since rectangles are processed in insertion order, ties cannot occur, and the highest index is always well-defined.