library_checker/data_structure/
area_of_union_of_rectangles.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::RangeMinCountRangeAdd,
4    algorithm::SliceSortExt,
5    data_structure::{LazySegmentTree, StaticSearch},
6};
7
8#[verify::library_checker("area_of_union_of_rectangles")]
9pub fn area_of_union_of_rectangles(reader: impl Read, writer: impl Write) {
10    prepare_io!(buffered; reader, writer);
11    sc!(n, rectangles: [(u32, u32, u32, u32); n]);
12    let endpoints: Vec<_> = rectangles.iter().flat_map(|&(_, d, _, u)| [d, u]).collect();
13    let mut ys = endpoints.clone();
14    ys.radix_sort_by_key(|&y| y);
15    ys.dedup();
16    let search = StaticSearch::from_sorted(&ys);
17    let mut positions = vec![0; endpoints.len()];
18    search.lower_bound_batch(&endpoints, &mut positions);
19    let mut events: Vec<_> = rectangles
20        .into_iter()
21        .zip(positions.as_chunks().0)
22        .flat_map(|((l, _, r, _), &[d, u])| {
23            let d = d as u32;
24            let u = u as u32;
25            [(l, d, u, 1), (r, d, u, -1)]
26        })
27        .collect();
28    events.radix_sort_by_key(|&(x, ..)| x);
29    let mut seg = LazySegmentTree::<RangeMinCountRangeAdd<i32>>::from_vec(
30        ys.windows(2).map(|w| (0, (w[1] - w[0]) as usize)).collect(),
31    );
32    let height = (ys[ys.len() - 1] - ys[0]) as usize;
33    let mut prev_x = 0;
34    let mut area = 0u64;
35    for (x, d, u, delta) in events {
36        let (minimum, count) = seg.fold_all();
37        let covered = height - if minimum == 0 { count } else { 0 };
38        area += (x - prev_x) as u64 * covered as u64;
39        seg.update(d as usize..u as usize, delta);
40        prev_x = x;
41    }
42    pp!(area);
43}
library_checker/data_structure/area_of_union_of_rectangles.rs

library_checker/data_structure/
area_of_union_of_rectangles.rs
