Submission #15341040


Source Code Expand

Copy
use proconio::*;
use proconio::marker::*;

#[fastout]
fn run() {
    input! {
        h: usize,
        w: usize,
        k: u8,
        ini: [[u8; w]; h],
        q: usize,
        ask: [(u8, Usize1, Usize1, Usize1, Usize1); q],
    }
    let mut a = vec![vec![0u32; w + 1]; h + 1];
    let mut b = vec![vec![false; w]; h];
    let mut ans = vec![(0, 0); q];
    for k in 0..k {
        for (a, (b, ini)) in a.iter_mut().zip(b.iter_mut().zip(ini.iter())) {
            for (a, (b, ini)) in a.iter_mut().zip(b.iter_mut().zip(ini.iter())) {
                let v = *ini == k;
                *a = v as u32;
                *b = v;
            }
        }
        for i in (0..h).rev() {
            for j in (0..w).rev() {
                a[i][j] += a[i + 1][j] + a[i][j + 1] - a[i + 1][j + 1];
            }
        }
        for (ans, &(op, x, y, z, w)) in ans.iter_mut().zip(ask.iter()) {
            if op == 1 {
                if b[x][y] != b[z][w] {
                    if x != z {
                        let r = std::cmp::max(x, z);
                        let xor = x ^ z;
                        let diff = b[xor ^ r][w] as u32 - b[r][w] as u32;
                        for a in a[r].iter_mut().take(w + 1) {
                            *a += diff;
                        }
                    } else {
                        let c = std::cmp::max(y, w);
                        let xor = y ^ w;
                        let diff = b[x][xor ^ c] as u32 - b[x][c] as u32;
                        for a in a.iter_mut().take(x + 1) {
                            a[c] += diff;
                        }
                    }
                    let s = b[x][y];
                    b[x][y] = b[z][w];
                    b[z][w] = s;
                }
            } else {
                let val = a[x][y] - a[z + 1][y] - a[x][w + 1] + a[z + 1][w + 1];
                *ans = std::cmp::max(*ans, (val, k + 1));
            }
        }
    }
    for &(cnt, k) in ans.iter().filter(|p| p.0 > 0) {
        println!("{} {}", k, cnt);
    }
}

fn main() {
    run();
}

Submission Info

Submission Time
Task C - 宝探し 2
User sansen
Language Rust (1.42.0)
Score 0
Code Size 2137 Byte
Status
Exec Time 242 ms
Memory 10720 KB

Judge Result

Set Name Score / Max Score Test Cases
All 0 / 100 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 30-max_query-00, 30-max_query-01, 30-max_query-02
Case Name Status Exec Time Memory
00-sample-00 7 ms 2096 KB
00-sample-01 1 ms 2000 KB
10-random_small-00 31 ms 6988 KB
10-random_small-01 5 ms 2292 KB
10-random_small-02 45 ms 3444 KB
10-random_small-03 10 ms 2204 KB
10-random_small-04 48 ms 7204 KB
10-random_small-05 126 ms 7600 KB
10-random_small-06 9 ms 2444 KB
10-random_small-07 31 ms 4960 KB
10-random_small-08 15 ms 2240 KB
20-random_large-00 240 ms 10600 KB
20-random_large-01 240 ms 10612 KB
20-random_large-02 241 ms 10632 KB
20-random_large-03 241 ms 10568 KB
20-random_large-04 242 ms 10720 KB
30-max_query-00 206 ms 10640 KB
30-max_query-01 204 ms 10564 KB
30-max_query-02 203 ms 10548 KB