結果

問題 No.2002 Range Swap Query
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-09-17 17:54:25
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 7 ms
6,944 KB
testcase_09 AC 13 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 9 ms
6,944 KB
testcase_12 AC 606 ms
54,112 KB
testcase_13 AC 472 ms
54,028 KB
testcase_14 AC 533 ms
54,000 KB
testcase_15 AC 418 ms
52,596 KB
testcase_16 AC 289 ms
31,080 KB
testcase_17 AC 460 ms
53,984 KB
testcase_18 AC 292 ms
25,568 KB
testcase_19 AC 400 ms
45,508 KB
testcase_20 AC 278 ms
27,300 KB
testcase_21 AC 273 ms
19,748 KB
権限があれば一括ダウンロードができます

ソースコード

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