結果

問題 No.3072 Speedrun Query
ユーザー urectanc
提出日時 2025-03-24 18:51:15
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 111 ms / 2,500 ms
コード長 1,734 bytes
コンパイル時間 13,728 ms
コンパイル使用メモリ 403,124 KB
実行使用メモリ 33,392 KB
最終ジャッジ日時 2025-03-24 18:51:35
合計ジャッジ時間 17,941 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::fmt::Write;

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

fn main() {
    input! {
        n: usize, k_a: usize, k_b: usize,
        a: [Usize1; k_a],
        b: [Usize1; k_b],
        q: usize,
        query: [(Usize1, Usize1); q],
    }

    let dist = |a: &[usize]| {
        let mut res = vec![!0; n];
        let k = a.len();
        let mut j = 0;
        for i in 0..n {
            if j > 0 {
                res[i] = res[i].min(i.abs_diff(a[j - 1]));
            }
            if j < k {
                res[i] = res[i].min(i.abs_diff(a[j]));
            }
            if j < k && i == a[j] {
                j += 1;
            }
        }
        res
    };

    let dist_a = dist(&a);
    let dist_b = dist(&b);

    let dist_ab = {
        let mut mixed = Vec::with_capacity(k_a + k_b);
        for &a in &a {
            mixed.push((a, true));
        }
        for &b in &b {
            mixed.push((b, false));
        }
        mixed.sort_unstable_by_key(|t| t.0);

        mixed
            .windows(2)
            .filter_map(|w| {
                if w[0].1 != w[1].1 {
                    Some(w[1].0 - w[0].0)
                } else {
                    None
                }
            })
            .min()
            .unwrap()
    };
    eprintln!("{:?}", dist_ab);

    let mut output = String::new();
    for (s, t) in query {
        let d = s.abs_diff(t);
        let d_a = dist_a[s] + dist_a[t];
        let d_b = dist_b[s] + dist_b[t];
        let d_ab = dist_a[s] + dist_ab + dist_b[t];
        let d_ba = dist_b[s] + dist_ab + dist_a[t];
        let ans = d.min(d_a).min(d_b).min(d_ab).min(d_ba);
        writeln!(&mut output, "{ans}").unwrap();
    }

    println!("{}", output.trim_end());
}
0