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

aizu_online_judge/dsl/
dsl_4_a.rs
