Submission #15340826


Source Code Expand

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

#[fastout]
fn run() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        a: [[Usize1; w]; h],
        q: usize,
        ask: [(u8, Usize1, Usize1, Usize1, Usize1); q],
    }
    let mut ans = vec![(0, 0); q];
    for k in 0..k {
        let mut a: Vec<Vec<u32>> = a.iter().map(|a| a.iter().map(|a| (*a == k) as u32).collect()).collect();
        let mut b = a.clone();
        for a in a.iter_mut() {
            a.push(0);
        }
        a.push(vec![0; w + 1]);
        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;
                        for a in a[r].iter_mut().take(w + 1) {
                            *a += b[xor ^ r][w] - b[r][w];
                        }
                    } else {
                        let c = std::cmp::max(y, w);
                        let xor = y ^ w;
                        for a in a.iter_mut().take(x + 1) {
                            a[c] += b[x][xor ^ c] - b[x][c];
                        }
                    }
                    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 1901 Byte
Status
Exec Time 433 ms
Memory 14860 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 9 ms 1948 KB
00-sample-01 2 ms 2116 KB
10-random_small-00 38 ms 7864 KB
10-random_small-01 8 ms 2324 KB
10-random_small-02 46 ms 3400 KB
10-random_small-03 11 ms 2524 KB
10-random_small-04 43 ms 7752 KB
10-random_small-05 125 ms 8388 KB
10-random_small-06 9 ms 2780 KB
10-random_small-07 29 ms 5368 KB
10-random_small-08 18 ms 2472 KB
20-random_large-00 432 ms 14796 KB
20-random_large-01 429 ms 14848 KB
20-random_large-02 432 ms 14860 KB
20-random_large-03 425 ms 14844 KB
20-random_large-04 433 ms 14808 KB
30-max_query-00 371 ms 14692 KB
30-max_query-01 370 ms 14808 KB
30-max_query-02 368 ms 14748 KB