// https://kth.kattis.com/problems/kth.javap.windows use std::{ io::{stdin, Read}, iter::repeat, }; #[derive(Debug, Clone, Copy, PartialEq, Eq)] enum Tile { Covered, Empty, Split(u32), } use Tile::*; trait Tiles { fn fill(&mut self, i: u32, tile: Coord, coord: Coord); fn count(&self, i: u32, tile: Coord) -> usize; } impl Tiles for Vec { fn fill(&mut self, i: u32, tile: Coord, coord: Coord) { if self[i as usize] == Covered { return; } if coord.x2 <= tile.x1 || coord.x1 >= tile.x2 || coord.y2 <= tile.y1 || coord.y1 >= tile.y2 { return; } if coord.x1 <= tile.x1 && coord.x2 >= tile.x2 && coord.y1 <= tile.y1 && coord.y2 >= tile.y2 { self[i as usize] = Covered; return; } let c = match self[i as usize] { Empty => { let c = self.len() as u32; self[i as usize] = Split(c); self.extend(repeat(Empty).take(4)); c } Split(c) => c, _ => unreachable!(), }; for q in 0..4 { self.fill(c + q, tile.quadrant(q), coord); } } fn count(&self, i: u32, tile: Coord) -> usize { match self[i as usize] { Covered => (tile.x2 - tile.x1) as usize * (tile.y2 - tile.y1) as usize, Empty => 0, Split(c) => (0..4).map(|q| self.count(c + q, tile.quadrant(q))).sum(), } } } #[derive(Clone, Copy, PartialEq, Eq)] struct Coord { x1: u16, y1: u16, x2: u16, y2: u16, } impl Coord { fn mid(&self) -> (u16, u16) { ( self.x1 + (self.x2 - self.x1) / 2, self.y1 + (self.y2 - self.y1) / 2, ) } fn quadrant(mut self, q: u32) -> Self { let mid = self.mid(); let x = if q % 2 == 0 { &mut self.x1 } else { &mut self.x2 }; let y = if q < 2 { &mut self.y1 } else { &mut self.y2 }; *x = mid.0; *y = mid.1; self } } fn main() { let mut input = String::new(); stdin().lock().read_to_string(&mut input).unwrap(); let mut ints = input .split(|c| c == ' ' || c == '\n') .flat_map(|i| i.trim().parse::().ok()); let mut get = || ints.next().unwrap(); let mut tiles = Vec::with_capacity(33_000_000); tiles.push(Empty); let screen = Coord { x1: 0, y1: 0, x2: 10001, y2: 10001, }; let n = get(); for _ in 0..n { let coord = Coord { x1: get(), y1: get(), x2: get(), y2: get(), }; tiles.fill(0, screen, coord); } println!("{}", tiles.count(0, screen)); }