結果

問題 No.440 2次元チワワ問題
コンテスト
ユーザー titia
提出日時 2025-01-15 03:17:19
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,120 bytes
コンパイル時間 19,729 ms
コンパイル使用メモリ 403,936 KB
実行使用メモリ 812,436 KB
最終ジャッジ日時 2025-01-15 03:17:54
合計ジャッジ時間 26,466 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io;

fn main() {
    let stdin = io::stdin();
    let mut input = String::new();
    stdin.read_line(&mut input).unwrap();
    let dims: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (h, w) = (dims[0], dims[1]);

    let mut map = Vec::new();
    for _ in 0..h {
        input.clear();
        stdin.read_line(&mut input).unwrap();
        map.push(input.trim().chars().collect::<Vec<char>>());
    }

    let mut score = vec![0i64; h * w * w];
    let mut score2 = vec![0i64; w * h * h];

    fn calc(h: usize, l: usize, w: usize, map: &Vec<Vec<char>>, score: &mut Vec<i64>) {
        let mut c = 0i64;
        let mut cw = 0i64;
        let mut now = 0i64;
        for i in l..w {
            if map[h][i] == 'c' {
                c += 1;
            } else {
                now += cw;
                cw += c;
            }
            score[h * w * w + l * w + i] += now;
        }
    }

    fn calc2(h: usize, r: usize, w: usize, map: &Vec<Vec<char>>, score: &mut Vec<i64>) {
        let mut c = 0i64;
        let mut cw = 0i64;
        let mut now = 0i64;
        for i in (0..=r).rev() {
            if map[h][i] == 'c' {
                c += 1;
            } else {
                now += cw;
                cw += c;
            }
            score[h * w * w + i * w + r] += now;
        }
    }

    fn calc3(w: usize, l: usize, h: usize, map: &Vec<Vec<char>>, score2: &mut Vec<i64>) {
        let mut c = 0i64;
        let mut cw = 0i64;
        let mut now = 0i64;
        for i in l..h {
            if map[i][w] == 'c' {
                c += 1;
            } else {
                now += cw;
                cw += c;
            }
            score2[w * h * h + l * h + i] += now;
        }
    }

    fn calc4(w: usize, r: usize, h: usize, map: &Vec<Vec<char>>, score2: &mut Vec<i64>) {
        let mut c = 0i64;
        let mut cw = 0i64;
        let mut now = 0i64;
        for i in (0..=r).rev() {
            if map[i][w] == 'c' {
                c += 1;
            } else {
                now += cw;
                cw += c;
            }
            score2[w * h * h + i * h + r] += now;
        }
    }

    for i in 0..h {
        for j in 0..w {
            calc(i, j, w, &map, &mut score);
            calc2(i, j, w, &map, &mut score);
        }
    }

    for i in 0..w {
        for j in 0..h {
            calc3(i, j, h, &map, &mut score2);
            calc4(i, j, h, &map, &mut score2);
        }
    }

    input.clear();
    stdin.read_line(&mut input).unwrap();
    let q: usize = input.trim().parse().unwrap();

    for _ in 0..q {
        input.clear();
        stdin.read_line(&mut input).unwrap();
        let query: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
        let (a, b, c, d) = (query[0] - 1, query[1] - 1, query[2] - 1, query[3] - 1);

        let mut ans = 0i64;

        for i in a..=c {
            ans += score[i * w * w + b * w + d];
        }

        for i in b..=d {
            ans += score2[i * h * h + a * h + c];
        }

        println!("{}", ans);
    }
}
0