AtCoder Beginner Contest 432 D

https://atcoder.jp/contests/abc432/tasks/abc432_d

14回なので最大でも16384個の長方形しかできないので、それらが繋がっているかどうかを調べます。

// Suddenly, A Tempest
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// UnionFind ////////////////////

type Node = usize;

use std::cmp::max;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn connect(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        let mut v = v0;
        while self.parents[v] != v {
            v = self.parents[v]
        }
        v
    }
}

fn add_edge(uf: &mut UnionFind, u: Node, v: Node) {
    let r1 = uf.root(u);
    let r2 = uf.root(v);
    if r1 != r2 {
        uf.connect(u, v);
    }
}


//////////////////// Rect ////////////////////

// [left, right, bottom, top]
type Rect = [i32; 4];

fn rect_area(rect: &Rect) -> i64 {
    ((rect[1] - rect[0]) as i64) * ((rect[3] - rect[2]) as i64)
}

fn move_toward(rect: &Rect, (dx, dy): (i32, i32)) -> Rect {
    [rect[0] + dx, rect[1] + dx, rect[2] + dy, rect[3] + dy]
}


//////////////////// Storm ////////////////////

struct Storm {
    C: char,
    A: i32,
    B: i32
}

impl Storm {
    fn divide(&self, rect: &Rect) -> Vec<Rect> {
        if self.C == 'X' {
            if rect[1] <= self.A {
                vec![move_toward(&rect, (0, -self.B))]
            }
            else if self.A <= rect[0] {
                vec![move_toward(&rect, (0,  self.B))]
            }
            else {
                let rect1 = [rect[0], self.A, rect[2], rect[3]];
                let rect2 = [self.A, rect[1], rect[2], rect[3]];
                vec![move_toward(&rect1, (0, -self.B)),
                     move_toward(&rect2, (0,  self.B))]
            }
        }
        else {
            if rect[3] <= self.A {
                vec![move_toward(&rect, (-self.B, 0))]
            }
            else if self.A <= rect[2] {
                vec![move_toward(&rect, ( self.B, 0))]
            }
            else {
                let rect1 = [rect[0], rect[1], rect[2], self.A];
                let rect2 = [rect[0], rect[1], self.A, rect[3]];
                vec![move_toward(&rect1, (-self.B, 0)),
                     move_toward(&rect2, ( self.B, 0))]
            }
        }
    }
    
    fn read() -> Storm {
        let v: Vec<String> = read_vec();
        let C: char = v[0].chars().next().unwrap();
        let A: i32 = v[1].parse().unwrap();
        let B: i32 = v[2].parse().unwrap();
        Storm { C, A, B }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (i32, i32, Vec<Storm>) {
    let v: Vec<i32> = read_vec();
    let (N, X, Y) = (v[0], v[1], v[2]);
    let storms: Vec<Storm> = (0..N).map(|_| Storm::read()).collect();
    (X, Y, storms)
}

fn update(storm: Storm, rects: Vec<Rect>) -> Vec<Rect> {
    let mut new_rects = vec![];
    for rect in rects.iter() {
        let rects = storm.divide(rect);
        new_rects.extend(rects)
    }
    new_rects
}

fn count_num_components(rects: &Vec<Rect>) -> Vec<i64> {
    fn intersects(xs1: &[i32], xs2: &[i32]) -> bool {
        (xs1[0] < xs2[0] && xs2[0] < xs1[1]) ||
        (xs1[0] < xs2[1] && xs2[1] < xs1[1]) ||
        (xs2[0] < xs1[0] && xs1[0] < xs2[1]) ||
        (xs2[0] < xs1[1] && xs1[1] < xs2[1]) ||
        (xs1[0] == xs2[0] && xs1[1] == xs2[1])
    }
    
    let N = rects.len();
    let mut lefts: HashMap<i32, Vec<usize>> = HashMap::new();
    let mut bottoms: HashMap<i32, Vec<usize>> = HashMap::new();
    for i in 0..N {
        let ex = lefts.entry(rects[i][0]).or_insert(vec![]);
        (*ex).push(i);
        let ey = bottoms.entry(rects[i][2]).or_insert(vec![]);
        (*ey).push(i);
    }
    
    let mut uf = UnionFind::new(N);
    for i in 0..N {
        if let Some(v) = lefts.get(&rects[i][1]) {
            for &j in v.iter() {
                if intersects(&rects[i][2..], &rects[j][2..]) {
                    add_edge(&mut uf, i, j)
                }
            }
        }
        if let Some(v) = bottoms.get(&rects[i][3]) {
            for &j in v.iter() {
                if intersects(&rects[i][..2], &rects[j][..2]) {
                    add_edge(&mut uf, i, j)
                }
            }
        }
    }
    
    let mut counter: HashMap<usize, i64> = HashMap::new();
    for i in 0..N {
        let e = counter.entry(uf.root(i)).or_insert(0);
        *e += rect_area(&rects[i])
    }
    let mut ns: Vec<i64> = counter.into_iter().map(|(_, n)| n).collect();
    ns.sort();
    ns
}

fn F(X: i32, Y: i32, storms: Vec<Storm>) {
    let mut rects: Vec<Rect> = vec![[0, X, 0, Y]];
    for storm in storms {
        rects = update(storm, rects);
    }
    let ns = count_num_components(&rects);
    println!("{}", ns.len());
    println!("{}", ns.iter().map(|n| n.to_string()).
                                        collect::<Vec<_>>().join(" "))
}

fn main() {
    let (X, Y, storms) = read_input();
    F(X, Y, storms)
}