Submission #15341051


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 1..=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));
            }
        }
    }
    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 100
Code Size 2134 Byte
Status
Exec Time 228 ms
Memory 10676 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 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 2176 KB
00-sample-01 2 ms 2084 KB
10-random_small-00 32 ms 6948 KB
10-random_small-01 9 ms 2320 KB
10-random_small-02 39 ms 3464 KB
10-random_small-03 6 ms 2296 KB
10-random_small-04 44 ms 7120 KB
10-random_small-05 112 ms 7588 KB
10-random_small-06 9 ms 2604 KB
10-random_small-07 32 ms 4900 KB
10-random_small-08 13 ms 2304 KB
20-random_large-00 227 ms 10588 KB
20-random_large-01 226 ms 10612 KB
20-random_large-02 226 ms 10528 KB
20-random_large-03 228 ms 10676 KB
20-random_large-04 226 ms 10596 KB
30-max_query-00 193 ms 10592 KB
30-max_query-01 199 ms 10576 KB
30-max_query-02 197 ms 10568 KB