Area Covered by Posters
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
N axis-aligned rectangular posters are stuck on a board; rects[i] = [x1, y1, x2, y2] has lower-left corner (x1, y1) and
upper-right corner (x2, y2). Posters may overlap. Return the total area covered by at least one poster (overlaps count
once).
Examples
| rects | result |
|---|---|
[[0, 0, 2, 2], [1, 1, 3, 3]] | 7 |
[[0, 0, 4, 1], [0, 0, 1, 4], [3, 0, 4, 4], [0, 3, 4, 4]] | 12 |
[[0, 0, 1000000000, 1000000000], [5, 5, 6, 6]] | 1000000000000000000 |
Example 1 — two squares of area 4 overlapping in area 1: .
Example 2 — a frame: the outline minus the empty middle.
Example 3 — the small poster lies inside the big one; the answer can far exceed 32 bits.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(rects: int[][]) → long
Constraints
-
rects.length rects[i] = [x1, y1, x2, y2], ,- The answer may not fit in 32 bits.
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| rects | Expected |
|---|---|
[[0,0,2,2],[1,1,3,3]] | 7 |
[[0,0,4,1],[0,0,1,4],[3,0,4,4],[0,3,4,4]] | 12 |
[[0,0,1000000000,1000000000],[5,5,6,6]] | 1000000000000000000 |
Hint
Hint
Sweep a vertical line from left to right: a poster's y-interval enters at x1 and leaves at x2, and between consecutive
events the covered y-length is constant, so area = Σ covered length × gap. Keep the covered length in a segment tree over the
compressed y coordinates where each node stores cnt (posters covering the whole node, added only to the
canonical nodes, never pushed down) and len (full width if cnt > 0, else the children's sum). The root's len is the
covered length. This is ; rescanning every poster per slab is and exceeds the time limit. Use 64-bit
integers.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 312 ms | estimated |
| C++ (GCC, gnu++23) | 312 ms | derived |
| Python 3.13 | 3486 ms | derived |
| Java 25 | 1830 ms | derived |
| Kotlin 2.4 (JVM) | 1624 ms | estimated |
| C# 14 (.NET 10) | 1624 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |