結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー magurofly
提出日時 2025-04-19 10:36:18
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,345 bytes
コンパイル時間 19,491 ms
コンパイル使用メモリ 385,720 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-19 10:36:44
合計ジャッジ時間 18,777 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::BTreeMap;

use proconio::input;

fn main() {
    input!(n: i64, q: usize);

    // ranges[&l] = (r, a, b)
    let mut ranges = BTreeMap::new();
    ranges.insert(1, (n + 1, 1, 0));

    for _ in 0 .. q {
        // eprintln!("*ranges = {:?}", ranges);

        input!(t: usize);
        if t == 1 {
            input!(x: i64);

            let (_l, &(_r, a, b)) = ranges.range(..= x).next_back().unwrap();

            // eprintln!("query1({x}): [{_l},{_r})-{a}-{b} ==> {}", (x - a).abs() + b);

            println!("{}", (x - a).abs() + b);
        } else {
            input!(a: i64, b: i64);

            {
                let (&_l1, &(_r1, a1, b1)) = ranges.range(..= a).next_back().unwrap();
                let cost_current = (a - a1).abs() + b1;
                if cost_current <= b {
                    // eprintln!("query2({a}, {b}): skipped because of [{_l1},{_r1})-{a1}-{b1}");
                    continue;
                }
            }

            // eprintln!("query2({a}, {b}):");

            let mut l = 1;
            let mut r = n + 1;

            // set left bound
            while let Some((&l1, &(_r1, a1, b1))) = ranges.range(..= a).next_back() {
                if (a1 - a).abs() + b <= b1 {
                    l = l1;
                    ranges.remove(&l1);
                    // eprintln!("    L: removed [{l1},{_r1})-{a1}-{b1}");
                    continue;
                }

                l = (a + a1 + b - b1) / 2;
                ranges.insert(l1, (l, a1, b1));
                // eprintln!("    L: updated [{l1},{_r1})-{a1}-{b1} ==> [{l1},{l})");
                break;
            }

            // set right bound
            while let Some((&l1, &(r1, a1, b1))) = ranges.range(a ..).next() {
                if (a1 - a).abs() + b <= b1 {
                    r = r1;
                    ranges.remove(&l1);
                    // eprintln!("    R: removed [{l1},{r1})-{a1}-{b1}");
                    continue;
                }

                r = (a + a1 - b + b1) / 2;
                ranges.remove(&l1);
                ranges.insert(r, (r1, a1, b1));
                // eprintln!("    R: updated [{l1},{r1})-{a1}-{b1} ==> [{r},{r1})");
            }

            ranges.insert(l, (r, a, b));
            // eprintln!("    inserted [{l},{r})-{a}-{b}");
        }
    }
}
0