Submission #15340941


Source Code Expand

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

#[fastout]
fn run() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        ini: [[Usize1; 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![0u32; 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) as u32;
                *a = v;
                *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] - b[r][w];
                        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] - b[x][c];
                        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 100
Code Size 2117 Byte
Status
Exec Time 255 ms
Memory 13812 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 2080 KB
00-sample-01 1 ms 2000 KB
10-random_small-00 34 ms 7768 KB
10-random_small-01 6 ms 2220 KB
10-random_small-02 43 ms 3412 KB
10-random_small-03 11 ms 2564 KB
10-random_small-04 41 ms 7692 KB
10-random_small-05 118 ms 8408 KB
10-random_small-06 11 ms 2748 KB
10-random_small-07 28 ms 5340 KB
10-random_small-08 15 ms 2500 KB
20-random_large-00 255 ms 13760 KB
20-random_large-01 250 ms 13644 KB
20-random_large-02 249 ms 13756 KB
20-random_large-03 249 ms 13812 KB
20-random_large-04 247 ms 13804 KB
30-max_query-00 215 ms 13720 KB
30-max_query-01 217 ms 13772 KB
30-max_query-02 216 ms 13744 KB