結果

問題 No.2786 RMQ on Grid Path
ユーザー Yukino DX.Yukino DX.
提出日時 2024-06-26 18:22:29
言語 Rust
(1.77.0)
結果
AC  
実行時間 2,891 ms / 6,000 ms
コード長 5,957 bytes
コンパイル時間 16,634 ms
コンパイル使用メモリ 377,820 KB
実行使用メモリ 40,224 KB
最終ジャッジ日時 2024-06-26 18:24:01
合計ジャッジ時間 67,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2,732 ms
40,156 KB
testcase_13 AC 2,780 ms
40,224 KB
testcase_14 AC 2,780 ms
40,096 KB
testcase_15 AC 2,786 ms
40,212 KB
testcase_16 AC 2,772 ms
40,192 KB
testcase_17 AC 2,891 ms
40,116 KB
testcase_18 AC 2,852 ms
40,220 KB
testcase_19 AC 2,848 ms
40,088 KB
testcase_20 AC 2,785 ms
40,088 KB
testcase_21 AC 2,672 ms
40,212 KB
testcase_22 AC 2,396 ms
39,624 KB
testcase_23 AC 2,365 ms
39,620 KB
testcase_24 AC 1,178 ms
34,396 KB
testcase_25 AC 1,185 ms
34,404 KB
testcase_26 AC 1,169 ms
34,376 KB
testcase_27 AC 748 ms
16,604 KB
testcase_28 AC 671 ms
17,576 KB
testcase_29 AC 2,227 ms
33,812 KB
testcase_30 AC 697 ms
16,248 KB
testcase_31 AC 72 ms
5,376 KB
testcase_32 AC 823 ms
32,852 KB
testcase_33 AC 278 ms
16,128 KB
testcase_34 AC 1,206 ms
38,604 KB
testcase_35 AC 1,204 ms
38,620 KB
testcase_36 AC 1,199 ms
38,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        h:usize,
        w:usize,
        a:[[usize;w];h],
        q:usize,
        sg:[(Usize1,Usize1,Usize1,Usize1);q],
    }

    let mut poss = vec![vec![]; h * w + 1];
    for i in 0..h * w {
        poss[a[i / w][i % w]].push(i);
    }

    let mut ranges = vec![(0, h * w); q];
    while ranges.iter().any(|&(ng, ok)| ok - ng > 1) {
        let mut ms = (0..q)
            .map(|i| ((ranges[i].0 + ranges[i].1) / 2, i))
            .collect::<Vec<_>>();
        ms.sort();

        let mut uf = UnionFindTree::new(h * w);
        let mut j = 0;
        for i in 0..=h * w {
            for &p in poss[i].iter() {
                for Pos { x: nx, y: ny } in Pos::new(p / w, p % w).neigh4(h, w) {
                    if a[nx][ny] > i {
                        continue;
                    }
                    let np = nx * w + ny;
                    uf.unite(p, np);
                }
            }

            while j < q && ms[j].0 == i {
                if uf.same(
                    sg[ms[j].1].0 * w + sg[ms[j].1].1,
                    sg[ms[j].1].2 * w + sg[ms[j].1].3,
                ) {
                    ranges[ms[j].1].1 = i;
                } else {
                    ranges[ms[j].1].0 = i;
                }

                j += 1;
            }
        }
    }

    let ans = ranges.iter().map(|(_, ok)| *ok).collect::<Vec<_>>();
    for i in 0..q {
        println!("{}", ans[i]);
    }
}

use unionfindtree::*;
mod unionfindtree {
    pub struct UnionFindTree {
        par: Vec<usize>,
        rank: Vec<usize>,
        size: Vec<usize>,
    }

    impl UnionFindTree {
        pub fn new(n: usize) -> Self {
            Self {
                par: (0..n).collect::<Vec<_>>(),
                rank: vec![0; n],
                size: vec![1; n],
            }
        }

        #[allow(dead_code)]
        pub fn same(&mut self, v1: usize, v2: usize) -> bool {
            self.root(v1) == self.root(v2)
        }

        #[allow(dead_code)]
        pub fn size(&mut self, v: usize) -> usize {
            let v_root = self.root(v);
            self.size[v_root]
        }

        #[allow(dead_code)]
        pub fn root(&mut self, v: usize) -> usize {
            if self.par[v] != v {
                self.par[v] = self.root(self.par[v]);
            }

            self.par[v]
        }

        pub fn unite(&mut self, v1: usize, v2: usize) {
            let mut v1_root = self.root(v1);
            let mut v2_root = self.root(v2);
            if v1_root == v2_root {
                return;
            }

            if self.rank[v1_root] < self.rank[v2_root] {
                std::mem::swap(&mut v1_root, &mut v2_root);
            }

            self.par[v2_root] = v1_root;
            self.size[v1_root] += self.size[v2_root];

            if self.rank[v1_root] == self.rank[v2_root] {
                self.rank[v1_root] += 1;
            }
        }

        #[allow(dead_code)]
        pub fn nofcc(&mut self) -> usize {
            let n = self.par.len();
            (0..n)
                .map(|v| self.root(v))
                .collect::<std::collections::HashSet<usize>>()
                .len()
        }
    }
}

use grid_mgr::*;
mod grid_mgr {
    //[R,D,L,U]
    pub const DIR4: [(usize, usize); 4] = [(0, 1), (1, 0), (0, !0), (!0, 0)];
    pub const DIR8: [(usize, usize); 8] = [
        (1, 0),
        (1, !0),
        (0, !0),
        (!0, !0),
        (!0, 0),
        (!0, 1),
        (0, 1),
        (1, 1),
    ];

    pub struct Pos {
        pub x: usize,
        pub y: usize,
    }

    impl Pos {
        #[allow(dead_code)]
        pub fn new(x: usize, y: usize) -> Self {
            Self { x, y }
        }

        #[allow(dead_code)]
        pub fn neigh4<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a {
            DIR4.iter().filter_map(move |&(dx, dy)| {
                let nx = self.x.wrapping_add(dx);
                let ny = self.y.wrapping_add(dy);
                if nx < h && ny < w {
                    Some(Pos::new(nx, ny))
                } else {
                    None
                }
            })
        }

        #[allow(dead_code)]
        pub fn neigh8<'a>(&'a self, h: usize, w: usize) -> impl Iterator<Item = Pos> + 'a {
            DIR8.iter().filter_map(move |&(dx, dy)| {
                let nx = self.x.wrapping_add(dx);
                let ny = self.y.wrapping_add(dy);
                if nx < h && ny < w {
                    Some(Pos::new(nx, ny))
                } else {
                    None
                }
            })
        }

        #[allow(dead_code)]
        pub fn line<'a>(
            &'a self,
            h: usize,
            w: usize,
            dir: (usize, usize),
        ) -> impl Iterator<Item = Pos> + 'a {
            (0..).map_while(move |i| {
                let nx = self.x.wrapping_add(dir.0.wrapping_mul(i));
                let ny = self.y.wrapping_add(dir.1.wrapping_mul(i));
                if nx < h && ny < w {
                    Some(Pos::new(nx, ny))
                } else {
                    None
                }
            })
        }

        #[allow(dead_code)]
        pub fn _moveto(&self, h: usize, w: usize, dir: (usize, usize)) -> Option<Pos> {
            let nx = self.x.wrapping_add(dir.0);
            let ny = self.y.wrapping_add(dir.1);
            if nx < h && ny < w {
                Some(Pos::new(nx, ny))
            } else {
                None
            }
        }

        #[allow(dead_code)]
        pub fn moveto(&self, h: usize, w: usize, dir: char) -> Option<Pos> {
            match dir {
                'R' => self._moveto(h, w, DIR4[0]),
                'D' => self._moveto(h, w, DIR4[1]),
                'L' => self._moveto(h, w, DIR4[2]),
                'U' => self._moveto(h, w, DIR4[3]),
                _ => unreachable!(),
            }
        }
    }
}
0