結果

問題 No.2002 Range Swap Query
ユーザー urectanc
提出日時 2025-07-31 18:57:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,117 ms / 2,000 ms
コード長 1,859 bytes
コンパイル時間 13,114 ms
コンパイル使用メモリ 401,096 KB
実行使用メモリ 28,964 KB
最終ジャッジ日時 2025-07-31 18:57:43
合計ジャッジ時間 20,885 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::Usize1};
use std::fmt::Write;

fn main() {
    input! {
        n: usize, k: usize, q: usize,
        operations: [(Usize1, Usize1); k],
        queries: [(Usize1, usize, Usize1); q]
    }

    let bucket_width = (k as f64 / (2.0 / 3.0 * q as f64).sqrt()).ceil() as usize;

    let mut order = (0..q).collect::<Vec<_>>();
    order.sort_unstable_by_key(|&i| {
        let (l, r, _) = queries[i];
        (l / bucket_width, r)
    });
    let mut buckets = order
        .chunk_by(|&i, &j| queries[i].0 / bucket_width == queries[j].0 / bucket_width)
        .map(|bucket| bucket.into_iter().copied().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    for bucket in buckets.iter_mut().skip(1).step_by(2) {
        bucket.reverse();
    }

    let mut p = (0..n).collect::<Vec<_>>();
    let mut inv = p.clone();

    let mut ans = vec![!0; q];
    let mut cur_l = 0;
    let mut cur_r = 0;
    for i in buckets.into_iter().flatten() {
        let (l, r, x) = queries[i];
        while l < cur_l {
            cur_l -= 1;
            let (a, b) = operations[cur_l];
            inv.swap(a, b);
            p.swap(inv[a], inv[b]);
        }
        while cur_r < r {
            let (a, b) = operations[cur_r];
            inv.swap(p[a], p[b]);
            p.swap(a, b);
            cur_r += 1;
        }
        while cur_l < l {
            let (a, b) = operations[cur_l];
            inv.swap(a, b);
            p.swap(inv[a], inv[b]);
            cur_l += 1;
        }
        while r < cur_r {
            cur_r -= 1;
            let (a, b) = operations[cur_r];
            inv.swap(p[a], p[b]);
            p.swap(a, b);
        }

        ans[i] = p[x];
    }

    let mut output = String::new();
    for &ans in &ans {
        writeln!(&mut output, "{}", ans + 1).unwrap();
    }
    println!("{}", output.trim_end());
}
0