結果

問題 No.875 Range Mindex Query
ユーザー wesriverywesrivery
提出日時 2019-09-06 23:52:02
言語 Rust
(1.77.0)
結果
MLE  
実行時間 -
コード長 4,137 bytes
コンパイル時間 2,226 ms
コンパイル使用メモリ 143,216 KB
実行使用メモリ 812,168 KB
最終ジャッジ日時 2023-09-07 03:03:14
合計ジャッジ時間 4,973 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 MLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[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