Funcia
Lv.4coordinate-compressionsegment-treesweep-line

Area Covered by Posters

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

rectsresult
[[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: 4+4−1=74 + 4 - 1 = 7.

Example 2 — a frame: the 4×44 \times 4 outline minus the empty 2×22 \times 2 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

  • 1≤N=1 \le N = rects.length ≤100,000\le 100{,}000
  • rects[i] = [x1, y1, x2, y2], 0≤x1<x2≤1090 \le x1 < x2 \le 10^9, 0≤y1<y2≤1090 \le y1 < y2 \le 10^9
  • The answer may not fit in 32 bits.

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

rectsExpected
[[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 O(log⁡N)O(\log N) 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 O(Nlog⁡N)O(N \log N); rescanning every poster per slab is O(N2)O(N^2) and exceeds the time limit. Use 64-bit integers.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)312 msestimated
C++ (GCC, gnu++23)312 msderived
Python 3.133486 msderived
Java 251830 msderived
Kotlin 2.4 (JVM)1624 msestimated
C# 14 (.NET 10)1624 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.