Submission #15340638


Source Code Expand

Copy
type Index = i32;
type Weight = i32;
const ZERO: Weight = 0;

struct RectangleSum {
    point: Vec<(Index, Index)>,
    row: Vec<Index>,
    col: Vec<Vec<Index>>,
    bit: Vec<Vec<Weight>>,
}

impl RectangleSum {
    fn new() -> Self {
        RectangleSum {
            point: vec![],
            row: vec![],
            col: vec![],
            bit: vec![],
        }
    }
    fn add_point(&mut self, x: Index, y: Index) {
        self.point.push((x, y));
    }
    fn build(&mut self) {
        let mut row: Vec<_> = self.point.iter().map(|p| p.0).collect();
        row.sort();
        row.dedup();
        let mut a = vec![vec![]; row.len() + 1];
        for &(x, y) in self.point.iter() {
            let mut k = row.binary_search(&x).unwrap() + 1;
            while let Some(a) = a.get_mut(k) {
                a.push(y);
                k += k & (!k + 1);
            }
        }
        let mut bit = vec![vec![]; row.len() + 1];
        let mut col = vec![vec![]; row.len() + 1];
        for ((bit, col), a) in bit.iter_mut().zip(col.iter_mut()).zip(a.into_iter()).skip(1) {
            col.reserve(a.len());
            for &y in a.iter() {
                col.push(y);
            }
            col.sort();
            col.dedup();
            bit.resize(col.len() + 1, ZERO);
        }
        self.row = row;
        self.col = col;
        self.bit = bit;
    }
    fn add(&mut self, x: Index, y: Index, w: Weight) {
        let mut x = self.row.binary_search(&x).unwrap() + 1;
        while let Some(bit) = self.bit.get_mut(x) {
            let mut y = self.col[x].binary_search(&y).unwrap() + 1;
            while let Some(v) = bit.get_mut(y) {
                *v += w;
                y += y & (!y + 1);
            }
            x += x & (!x + 1);
        }
    }
    // (-inf, x] * (-inf * y] の和
    fn find(&self, x: Index, y: Index) -> Weight {
        let mut x = match self.row.binary_search(&x) {
            Ok(k) => k + 1,
            Err(k) => k,
        };
        let mut ans = ZERO;
        while x > 0 {
            let mut y = match self.col[x].binary_search(&y) {
                Ok(k) => k + 1,
                Err(k) => k,
            };
            let bit = &self.bit[x];
            while y > 0 {
                ans += bit[y];
                y -= y & (!y + 1);
            }
            x -= x & (!x + 1);
        }
        ans
    }
}

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 b: Vec<Vec<bool>> = a.iter().map(|a| a.iter().map(|a| *a == k).collect()).collect();
        for &(_, x, y, z, w) in ask.iter().filter(|p| p.0 == 1) {
            let p = b[x][y] || b[z][w];
            b[x][y] = p;
            b[z][w] = p;
        }
        let mut solver = RectangleSum::new();
        for (i, b) in b.iter().enumerate() {
            for (j, b) in b.iter().enumerate() {
                if *b {
                    solver.add_point(i as i32, j as i32);
                }
            }
        }
        solver.build();
        let mut b: Vec<Vec<bool>> = a.iter().map(|a| a.iter().map(|a| *a == k).collect()).collect();
        for (i, b) in b.iter().enumerate() {
            for (j, _) in b.iter().enumerate().filter(|p| *p.1) {
                solver.add(i as i32, j as i32, 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] {
                    b[x][y] ^= true;
                    b[z][w] ^= true;
                    solver.add(x as i32, y as i32, -1);
                    solver.add(z as i32, w as i32, 1);
                } else if !b[x][y] && b[z][w] {
                    b[x][y] ^= true;
                    b[z][w] ^= true;
                    solver.add(x as i32, y as i32, 1);
                    solver.add(z as i32, w as i32, -1);
                }
            } else {
                let (x, y, z, w) = (x as i32, y as i32, z as i32, w as i32);
                let val = solver.find(z, w) - solver.find(z, y - 1) - solver.find(x - 1, w) + solver.find(x - 1, y - 1);
                *ans = std::cmp::max(*ans, (val, k));
            }
        }
    }
    for &(cnt, k) in ans.iter().filter(|p| p.0 > 0) {
        println!("{} {}", k + 1, cnt);
    }
}

fn main() {
    run();
}

Submission Info

Submission Time
Task C - 宝探し 2
User sansen
Language Rust (1.42.0)
Score 0
Code Size 4675 Byte
Status
Exec Time 5513 ms
Memory 12868 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 4 ms 2216 KB
00-sample-01 2 ms 2152 KB
10-random_small-00 71 ms 7840 KB
10-random_small-01 11 ms 2264 KB
10-random_small-02 198 ms 3448 KB
10-random_small-03 20 ms 2712 KB
10-random_small-04 236 ms 7768 KB
10-random_small-05 2130 ms 8536 KB
10-random_small-06 28 ms 2868 KB
10-random_small-07 201 ms 5904 KB
10-random_small-08 80 ms 2528 KB
20-random_large-00 5081 ms 12632 KB
20-random_large-01 5086 ms 12744 KB
20-random_large-02 5047 ms 12780 KB
20-random_large-03 5086 ms 12736 KB
20-random_large-04 5083 ms 12868 KB
30-max_query-00 5513 ms 12656 KB
30-max_query-01 5513 ms 12788 KB
30-max_query-02 5513 ms 12768 KB