結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー wesrivery
提出日時 2019-09-06 23:52:02
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 4,137 bytes
記録
コンパイル時間 13,171 ms
コンパイル使用メモリ 377,916 KB
実行使用メモリ 796,928 KB
最終ジャッジ日時 2024-06-24 21:44:40
合計ジャッジ時間 15,525 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}


#[allow(unused_macros)]
macro_rules! invec {
    ( $ t : ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s
                .trim()
                .split_whitespace()
                .map(|s| s.parse::<$t>().unwrap())
                .collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }};
}

struct SegmentTree {
    from: usize,
    to: usize,
    value: u32,
    value_index: usize,
    left: Box<Option<SegmentTree>>,
    right: Box<Option<SegmentTree>>,
}

impl SegmentTree {
    fn query(&self, from: usize, to: usize) -> (usize, u32) {
        
        if from == self.from && to == self.to {
            return (self.value_index, self.value);
        }

        let boundary = (self.from + self.to) / 2;
        if from <= boundary && boundary < to {
            let (lindex, lval) = (*self.left).as_ref().unwrap().query(from, boundary);
            let (rindex, rval) = (*self.right).as_ref().unwrap().query(boundary + 1, to);
            if lval < rval {
                return (lindex, lval);
            } else {
                return (rindex, rval);
            }
        }

        if from <= boundary {
            return (*self.left).as_ref().unwrap().query(from, to);
        } else {
            return (*self.right).as_ref().unwrap().query(from, to);
        }
    }

    fn update(&mut self, index: usize, value: u32) {
        if index == self.from && index == self.to {
            self.value_index = index;
            self.value = value;
            return;
        }

        let boundary = (self.from + self.to) / 2;
        if index <= boundary {
            (*self.left).as_mut().unwrap().update(index, value);
        } else {
            (*self.right).as_mut().unwrap().update(index, value);
        }

        let left = (*self.left).as_ref().unwrap();
        let right = (*self.right).as_ref().unwrap();

        if left.value <= right.value {
            self.value_index = left.value_index;
            self.value = left.value;
        } else {
            self.value_index = right.value_index;
            self.value = right.value;
        };
    }
}

fn init(v: &Vec<u32>, from: usize, to: usize) -> SegmentTree {
    if from == to {
        return SegmentTree { from: from,
                             to: to,
                             value: v[from],
                             value_index: from,
                             left: Box::new(None),
                             right: Box::new(None), 
        };
    }

    let boundary = from + to / 2;
    let left = init(&v, from, boundary);
    let right = init(&v, boundary + 1, to);
    let (value, index) =
        if left.value <= right.value {
            (left.value, left.value_index)
        } else {
            (right.value, right.value_index)
        };

    return SegmentTree { from: from,
                         to: to,
                         value: value,
                         value_index: index,
                         left: Box::new(Some(left)),
                         right: Box::new(Some(right)),
    };
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, q) = input!(usize, usize);
    let mut a = invec!(u32);
    
    let mut tree = init(&a, 0, n - 1);

    for i in 0..q {
        let (op, l, r) = input!(u8, usize, usize);
        let l = l - 1;
        let r = r - 1;

        match op {
            1 => {
                let tmp = a[l];
                a[l] = a[r];
                a[r] = tmp;
                (&mut tree).update(l, a[l]);
                (&mut tree).update(r, a[r]);
            },
            2 => {
                println!("{}", tree.query(l, r).0 + 1);
            },
            _ => {},
        }
    }
}

fn main() {
    solve();
}
0