aizu_online_judge/dsl/
dsl_4_a.rs

1use competitive::prelude::*;
2
3#[verify::aizu_online_judge("DSL_4_A")]
4pub fn dsl_4_a(reader: impl Read, writer: impl Write) {
5    prepare_io!(reader, writer);
6    sc!(n, xyxy: [(i64, i64, i64, i64); n]);
7    let (mut xs, mut ys) = (Vec::with_capacity(2 * n), Vec::with_capacity(2 * n));
8    xs.extend(xyxy.iter().map(|t| t.0));
9    ys.extend(xyxy.iter().map(|t| t.1));
10    xs.extend(xyxy.iter().map(|t| t.2));
11    ys.extend(xyxy.iter().map(|t| t.3));
12    xs.sort_unstable();
13    ys.sort_unstable();
14    xs.dedup();
15    ys.dedup();
16    let mut qs = vec![vec![]; xs.len()];
17    for (x1, y1, x2, y2) in xyxy {
18        let x1 = xs.binary_search(&x1).unwrap_or_else(|x| x);
19        let x2 = xs.binary_search(&x2).unwrap_or_else(|x| x);
20        let y1 = ys.binary_search(&y1).unwrap_or_else(|x| x);
21        let y2 = ys.binary_search(&y2).unwrap_or_else(|x| x);
22        qs[x1].push((y1, 1));
23        qs[x1].push((y2, -1));
24        qs[x2].push((y1, -1));
25        qs[x2].push((y2, 1));
26    }
27    let mut ans = 0;
28    let mut acc = vec![0; ys.len()];
29    for i in 0..xs.len() - 1 {
30        let d = xs[i + 1] - xs[i];
31        let mut tmp = vec![0; ys.len()];
32        for &(j, c) in qs[i].iter() {
33            tmp[j] += c;
34        }
35        for j in 0..ys.len() - 1 {
36            tmp[j + 1] += tmp[j];
37        }
38        for (acc, tmp) in acc.iter_mut().zip(tmp.iter_mut()) {
39            *acc += *tmp;
40        }
41        for j in 0..ys.len() - 1 {
42            if acc[j] > 0 {
43                ans += d * (ys[j + 1] - ys[j]);
44            }
45        }
46    }
47    pp!(ans);
48}
aizu_online_judge/dsl/dsl_4_a.rs

aizu_online_judge/dsl/
dsl_4_a.rs
