結果

問題 No.3709 Unknown Treasure
コンテスト
ユーザー norioc
提出日時 2026-09-22 20:08:26
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 64 ms / 2,000 ms
+ 198µs
コード長 2,492 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,565 ms
コンパイル使用メモリ 204,524 KB
実行使用メモリ 49,128 KB
最終ジャッジ日時 2026-09-22 20:08:34
合計ジャッジ時間 7,750 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variant `Size` is never constructed
  --> src/main.rs:31:5
   |
27 | enum Rect {
   |      ---- variant in this enum
...
31 |     Size(usize, usize, usize, usize, i64),
   |     ^^^^
   |
   = note: `Rect` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

ソースコード

diff #
raw source code 

#![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<Vec<i64>> {
    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);
}
0