Initial commit

1 files changed, 119 insertions, 0 deletions

diff --git a/kattis-kth-javap-windows/src/main.rs b/kattis-kth-javap-windows/src/main.rs
new file mode 100644
index 0000000..f10ba56
--- /dev/null
+++ b/kattis-kth-javap-windows/src/main.rs
@@ -0,0 +1,119 @@
+// 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<Tile> {
+    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::<u16>().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));
+}