結果

問題 No.2002 Range Swap Query
ユーザー LyricalMaestro
提出日時 2024-09-17 17:54:25
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 606 ms / 2,000 ms
コード長 1,748 bytes
コンパイル時間 12,047 ms
コンパイル使用メモリ 395,464 KB
実行使用メモリ 54,112 KB
最終ジャッジ日時 2024-09-17 17:54:48
合計ジャッジ時間 19,374 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

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


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

    //  操作iをしたときの
    let mut status = vec![0; n];
    let mut inv_status = vec![0; n + 1];
    for i in 0..n {
        status[i] = i + 1;
        inv_status[i + 1] = i;
    }

    let mut event_map = HashMap::new();
    for i in 0..q {
        let (l, r, x) = lrx[i];
        if !event_map.contains_key(&r) {
            let new_vec = Vec::new();
            event_map.insert(r, new_vec);
        }
        event_map.get_mut(&r).unwrap().push((l, x, i));
    }

    let mut ans_wait_map = HashMap::new();
    let mut answers = vec![0;q];

    for k0 in (0..k).rev() {
        let (a, b) = ab[k0];

        //  Rのものを入れる
        if event_map.contains_key(&k0) {
            for (l, x, i) in event_map[&k0].iter() {
                if !ans_wait_map.contains_key(l) {
                    let new_vec = Vec::new();
                    ans_wait_map.insert(l, new_vec);
                }
                let x_ = status[*x];
                ans_wait_map.get_mut(l).unwrap().push((x_, *i));
            }
        }

        //  入れ替え処理
        let x = status[a];
        let y = status[b];
        status[b] = x;
        status[a] = y;
        inv_status[x] = b;
        inv_status[y] = a;

        //  Lのもので答え出す
        if ans_wait_map.contains_key(&k0) {
            for (x_, i) in ans_wait_map[&k0].iter() {
                answers[*i] = 1 + inv_status[*x_];
            }
        }
    }

    for i in 0..q {
        println!("{}", answers[i]);
    }



}
0