#![allow(non_snake_case, unused_imports)] use std::cmp::{min, max}; use std::collections::{BinaryHeap, Bound, HashMap, HashSet, VecDeque}; use std::hash::Hash; use std::ops::RangeBounds; use ac_library::{Additive, Min, Segtree}; use proconio::{input, marker::Usize1, marker::Chars}; use itertools::Itertools; #[allow(unused_macros)] macro_rules! d { ( $( $x:expr ),* $(,)? ) => { eprintln!( concat!( $( stringify!($x), "={:?} " ),* ), $( $x ),* ); }; } #[allow(dead_code)] fn yn(b: bool) -> &'static str { if b { "Yes" } else { "No" } } #[derive(Debug, Clone, Copy, PartialEq, Eq)] enum Rect { /// 左上 (r1, c1) と 右下 (r2, c2)(両端を含む)と 重み v Corner(usize, usize, usize, usize, i64), /// 左上 (r, c) と 高さ・幅 (h, w) と 重み v Size(usize, usize, usize, usize, i64), } impl Rect { fn to_inclusive_bounds(&self) -> (usize, usize, usize, usize, i64) { match *self { Rect::Corner(r1, c1, r2, c2, v) => { assert!(r1 <= r2 && c1 <= c2, "Invalid corner range: ({}, {}) -> ({}, {})", r1, c1, r2, c2); (r1, c1, r2, c2, v) } Rect::Size(r, c, h, w, v) => { assert!(h > 0 && w > 0, "Invalid size: height={}, width={}", h, w); (r, c, r + h - 1, c + w - 1, v) } } } } fn imos2d(h: usize, w: usize, rects: &[Rect]) -> Vec> { let mut imos = vec![vec![0; w + 1]; h + 1]; for rect in rects { let (r1, c1, r2, c2, v) = rect.to_inclusive_bounds(); imos[r1][c1] += v; imos[r1][c2 + 1] -= v; imos[r2 + 1][c1] -= v; imos[r2 + 1][c2 + 1] += v; } for r in 0..h { for c in 1..w { imos[r][c] += imos[r][c - 1]; } } for r in 1..h { for c in 0..w { imos[r][c] += imos[r - 1][c]; } } imos.truncate(h); for row in &mut imos { row.truncate(w); } imos } fn main() { input! { H: usize, W: usize, N: usize, LRS: [(Usize1, Usize1, Usize1, Usize1); N], } let lrs = LRS.iter() .map(|&(r1, c1, r2, c2)| Rect::Corner(r1, c1, r2, c2, 1)) .collect_vec(); let g = imos2d(H, W, &lrs); let mut ans = 0; for i in 0..H { for j in 0..W { if g[i][j] == 0 { ans += 1; } } } println!("{}", ans); }