#1076634 (Rust) No.3116 More and more teleporter

• 問題: No.3116 More and more teleporter
• ユーザー: magurofly
• 提出日時: 2025-04-19 11:01:08
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 12,446 bytes
• コンパイル時間: 12,633 ms
• コンパイル使用メモリ: 398,832 KB
• 実行使用メモリ: 17,340 KB
• 最終ジャッジ日時: 2025-04-19 11:01:26
• 合計ジャッジ時間: 16,471 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 10 WA * 12

ソースコード

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

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

    let mut seg = SegTree::<H>::from(vec![(0, 0); n]);

    for _ in 0 .. q {
        input!(t: usize);
        if t == 1 {
            input!(x: Usize1);
            let (a, b) = seg.get(x);
            println!("{}", x.abs_diff(a) + b);
        } else {
            input!(x: Usize1, c: usize);

            // skip test
            {
                let (a, b) = seg.get(x);
                if x.abs_diff(a) + b <= c {
                    continue;
                }
            }
            
            let l = loop {
                let (a, b) = seg.get(0);
                if a.abs_diff(0) + b > x.abs_diff(0) + c {
                    break 0;
                }

                let mut ac = x;
                let mut wa = 0;
                while ac - wa > 1 {
                    let wj = (ac + wa) / 2;
                    let (a, b) = seg.get(wj);
                    if a.abs_diff(wj) + b > x.abs_diff(wj) + c {
                        ac = wj;
                    } else {
                        wa = wj;
                    }
                }

                break ac;
            };

            let r = loop {
                let mut ac = x + 1;
                let mut wa = n + 1;
                while wa - ac > 1 {
                    let wj = (ac + wa) / 2;
                    let (a, b) = seg.get(wj - 1);
                    if a.abs_diff(wj) + b > x.abs_diff(wj) + c {
                        ac = wj;
                    } else {
                        wa = wj;
                    }
                }

                break ac;
            };

            seg.apply_range(l .. r, &Some((x, c)));
        }
    }
}

enum H {}
impl SegTreeHelper for H {
    type S = (usize, usize);
    fn op(&x: &Self::S, &_y: &Self::S) -> Self::S {
        x
    }
    fn e() -> Self::S {
        (0, 0)
    }
    type F = Option<(usize, usize)>;
    fn map(&f: &Self::F, &x: &Self::S) -> Self::S {
        if let Some(a) = f {
            a
        } else {
            x
        }
    }
    fn compose(&f: &Self::F, &g: &Self::F) -> Self::F {
        g.or(f)
    }
    fn id() -> Self::F {
        None
    }
}

use segtree::*;
pub mod segtree {
    // Update: 2022-10-29 12:45
    #[allow(unused_variables)]
    pub trait SegTreeHelper {
        /// 要素の型
        type S: Clone;
        /// 要素の二項演算
        fn op(x: &Self::S, y: &Self::S) -> Self::S;
        /// 要素の単位元
        fn e() -> Self::S;
        /// 作用の型（使わない場合は `()` とする）
        type F: Clone + Default;
        /// 要素に作用させる
        fn map(f: &Self::F, x: &Self::S) -> Self::S { x.clone() }
        /// 作用の単位元
        fn id() -> Self::F { Self::F::default() }
        /// 作用の合成
        fn compose(f: &Self::F, g: &Self::F) -> Self::F { g.clone() }
        /// 再計算が必要か
        fn is_failed(x: &Self::S) -> bool { false }
    }
    
    pub struct SegTree<H: SegTreeHelper> {
        len: usize,
        size: usize,
        log: u32,
        data: UnsafeCell<Vec<H::S>>,
        lazy: UnsafeCell<Vec<H::F>>,
    }
    
    impl<H: SegTreeHelper> SegTree<H> {
        /// 長さが `len` 、要素が全て `H::e()` となるセグメント木を作成する。
        pub fn new(len: usize) -> Self {
            assert!(len > 0);
            let size = len.next_power_of_two();
            let log = size.trailing_zeros();
            Self {
                len, size, log,
                data: UnsafeCell::new(vec![H::e(); size * 2]),
                lazy: UnsafeCell::new(vec![H::id(); size]),
            }
        }
        
        /// `p` 番目の要素を取得する。
        pub fn get(&self, p: usize) -> H::S { self[p].clone() }
        
        /// `p` 番目の要素に `x` を代入する。
        pub fn set(&mut self, mut p: usize, x: H::S) {
            assert!(p < self.len);
            p += self.size;
            for i in (1 ..= self.log).rev() { self.push(p >> i); }
            self.data_mut()[p] = x;
            for i in 1 ..= self.log { self.update(p >> i); }
        }
        
        /// `range` に含まれる要素の積を取得する。
        pub fn prod(&self, range: impl RangeBounds<usize>) -> H::S {
            let (mut l, mut r) = self.range(range);
            assert!(l <= r);
            assert!(r <= self.len);
            l += self.size;
            r += self.size;
            if l == r { return H::e(); }
            for i in (1 ..= self.log).rev() {
                if (l >> i) << i != l { self.push(l >> i); }
                if (r >> i) << i != r { self.push(r - 1 >> i); }
            }
            let mut x = H::e();
            let mut y = H::e();
            while l < r {
                if l & 1 != 0 {
                    x = H::op(&x, &self.data()[l]);
                    l += 1;
                }
                l >>= 1;
                if r & 1 != 0 {
                    y = H::op(&self.data()[r - 1], &y);
                }
                r >>= 1;
            }
            H::op(&x, &y)
        }
        
        /// 全体の積を取得する。
        pub fn all_prod(&self) -> H::S { self.data()[1].clone() }
        
        /// `p` 番目の要素に `f` を適用する。
        pub fn apply(&mut self, p: usize, f: &H::F) {
            assert!(p < self.len);
            let x = H::map(f, &self[p]);
            self.set(p, x);
        }
        
        /// `range` に含まれる要素に `f` を適用する。
        pub fn apply_range(&mut self, range: impl RangeBounds<usize>, f: &H::F) {
            let (mut l, mut r) = self.range(range);
            assert!(l <= r);
            assert!(r <= self.len);
            l += self.size;
            r += self.size;
            for i in (1 ..= self.log).rev() {
                if (l >> i) << i != l { self.push(l >> i); }
                if (r >> i) << i != r { self.push(r - 1 >> i); }
            }
            let (l, r) = {
                let (l2, r2) = (l, r);
                while l < r {
                    if l & 1 != 0 {
                        self.all_apply(l, f);
                        l += 1;
                    }
                    l >>= 1;
                    if r & 1 != 0 {
                        self.all_apply(r - 1, f);
                    }
                    r >>= 1;
                }
                (l2, r2)
            };
            for i in 1 ..= self.log {
                if (l >> i) << i != l { self.update(l >> i); }
                if (r >> i) << i != r { self.update(r - 1 >> i); }
            }
        }

        pub fn max_right(&self, mut l: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
            assert!(l <= self.len);
            assert!(predicate(&H::e()));
            if l == self.len { return self.len; }
            l += self.size;
            for i in (1 ..= self.log).rev() { self.push(l >> i); }
            let mut x = H::e();
            loop {
                l >>= l.trailing_zeros();
                if !predicate(&H::op(&x, &self.data()[l])) {
                    while l < self.size {
                        self.push(l);
                        l *= 2;
                        let y = H::op(&x, &self.data()[l]);
                        if predicate(&y) {
                            x = y;
                            l += 1;
                        }
                    }
                    return l - self.size;
                }
                x = H::op(&x, &self.data()[l]);
                l += 1;
                if l.is_power_of_two() {
                    break;
                }
            }
            self.len
        }

        pub fn min_left(&self, mut r: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
            assert!(r <= self.len);
            assert!(predicate(&H::e()));
            if r == 0 { return 0; }
            r += self.size;
            for i in (1 ..= self.log).rev() { self.push(r - 1 >> i); }
            let mut x = H::e();
            loop {
                r -= 1;
                r >>= r.trailing_zeros();
                if !predicate(&H::op(&self.data()[r], &x)) {
                    while r < self.size {
                        self.push(r);
                        r = 2 * r + 1;
                        let y = H::op(&self.data()[r], &x);
                        if predicate(&y) {
                            x = y;
                            r -= 1;
                        }
                    }
                    return r + 1 - self.size;
                }
                x = H::op(&self.data()[r], &x);
                if r.is_power_of_two() {
                    break;
                }
            }
            0
        }
        
        fn update(&self, k: usize) {
            let z = H::op(&self.data()[k * 2], &self.data()[k * 2 + 1]);
            self.data_mut()[k] = z;
        }
        fn all_apply(&self, k: usize, f: &H::F) {
            let y = H::map(f, &self.data()[k]);
            self.data_mut()[k] = y;
            if k < self.size {
                let h = H::compose(&self.lazy()[k], f);
                self.lazy_mut()[k] = h;
                if H::is_failed(&self.data()[k]) {
                    self.push(k);
                    self.update(k);
                }
            }
        }
        fn push(&self, k: usize) {
            self.all_apply(2 * k, &self.lazy()[k]);
            self.all_apply(2 * k + 1, &self.lazy()[k]);
            self.lazy_mut()[k] = H::id();
        }
        fn range(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
            use Bound::*;
            (match range.start_bound() { Included(&p) => p, Excluded(&p) => p + 1, Unbounded => 0 },
            match range.end_bound() { Included(&p) => p + 1, Excluded(&p) => p, Unbounded => self.len })
        }
        fn data(&self) -> &Vec<H::S> { unsafe { &*self.data.get() } }
        fn lazy(&self) -> &Vec<H::F> { unsafe { &*self.lazy.get() } }
        fn data_mut(&self) -> &mut Vec<H::S> { unsafe { &mut *self.data.get() } }
        fn lazy_mut(&self) -> &mut Vec<H::F> { unsafe { &mut *self.lazy.get() } }
    }
    
    impl<H: SegTreeHelper> From<Vec<H::S>> for SegTree<H> {
        fn from(xs: Vec<H::S>) -> Self {
            let this = Self::new(xs.len());
            for (p, x) in xs.into_iter().enumerate() {
                this.data_mut()[this.size + p] = x;
            }
            for k in (1 .. this.size).rev() { this.update(k); }
            this
        }
    }

    impl<H: SegTreeHelper> FromIterator<H::S> for SegTree<H> {
        fn from_iter<T: IntoIterator<Item = H::S>>(iter: T) -> Self {
            Self::from(iter.into_iter().collect::<Vec<_>>())
        }
    }
    
    impl<H: SegTreeHelper> Index<usize> for SegTree<H> {
        type Output = H::S;
        fn index(&self, mut p: usize) -> &H::S {
            assert!(p < self.len);
            p += self.size;
            for i in (1 ..= self.log).rev() { self.push(p >> i); }
            &self.data()[p]
        }
    }

    impl<H: SegTreeHelper> Debug for SegTree<H> where H::S: Debug, H::F: Debug {
        fn fmt(&self, f: &mut Formatter<'_>) -> Result {
            f.write_fmt(format_args!("len={}, size={}, log={}, e={:?}, id={:?}\n", self.len, self.size, self.log, H::e(), H::id()))?;
            let data_str = self.data().iter().map(|x| format!("{:?}", x)).collect::<Vec<_>>();
            let lazy_str = self.lazy().iter().map(|x| format!("({:?})", x)).collect::<Vec<_>>();
            let unit_width = lazy_str.iter().chain(data_str.iter()).map(String::len).max().unwrap();
            fn print_row(f: &mut Formatter<'_>, raw_row: &[String], pad: usize) -> Result {
                let mut row = vec![];
                for raw in raw_row { row.push(format!("{:^width$}", raw, width=pad)); }
                f.write_str("|")?;
                f.write_str(&row.join("|"))?;
                f.write_str("|\n")
            }
            for i in 0 .. self.log {
                print_row(f, &data_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
                print_row(f, &lazy_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
            }
            print_row(f, &data_str[self.size ..], unit_width)?;
            Ok(())
        }
    }
    
    use std::{cell::*, fmt::*, iter::*, ops::*};
}