1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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));
}
|
