結果
問題 | No.875 Range Mindex Query |
ユーザー | wesrivery |
提出日時 | 2019-09-07 01:38:03 |
言語 | Rust (1.77.0 + proconio) |
結果 |
MLE
|
実行時間 | - |
コード長 | 4,721 bytes |
コンパイル時間 | 11,791 ms |
コンパイル使用メモリ | 391,680 KB |
実行使用メモリ | 793,600 KB |
最終ジャッジ日時 | 2024-06-25 00:39:08 |
合計ジャッジ時間 | 14,249 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 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 | -- | - |
ソースコード
#[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 Leaf { index: usize, value: u32, } struct Node { from: usize, to: usize, value: u32, index: usize, left: Box<SegmentTree>, right: Box<SegmentTree>, } enum SegmentTree { Leaf(Leaf), Node(Node), } impl SegmentTree { fn query(&self, from: usize, to: usize) -> (usize, u32) { match self { SegmentTree::Leaf(leaf) => (leaf.index, leaf.value), SegmentTree::Node(node) => { let boundary = (node.from + node.to) / 2; if from <= boundary && boundary < to { let (lindex, lval) = node.left.as_ref().query(from, boundary); let (rindex, rval) = node.right.as_ref().query(boundary + 1, to); if lval < rval { return (lindex, lval); } else { return (rindex, rval); } } if from <= boundary { return node.left.as_ref().query(from, to); } else { return node.right.as_ref().query(from, to); } } } } fn update(&mut self, index: usize, value: u32) { match self { SegmentTree::Leaf(leaf) => { leaf.index = index; leaf.value = value; return; }, SegmentTree::Node(node) => { let boundary = (node.from + node.to) / 2; if index <= boundary { node.left.as_mut().update(index, value); } else { node.right.as_mut().update(index, value); } let left = node.left.as_ref(); let right = node.right.as_ref(); if left.val() <= right.val() { node.index = left.ind(); node.value = left.val(); } else { node.index = right.ind(); node.value = right.val(); }; } } } fn new(v: &Vec<u32>, from: usize, to: usize) -> SegmentTree { if from == to { return SegmentTree::Leaf(Leaf { index: from, value: v[from], }); } let boundary = from + to / 2; let left = SegmentTree::new(&v, from, boundary); let right = SegmentTree::new(&v, boundary + 1, to); let (value, index) = if left.val() <= right.val() { (left.val(), left.ind()) } else { (right.val(), right.ind()) }; return SegmentTree::Node(Node { from: from, to: to, value: value, index: index, left: Box::new(left), right: Box::new(right), }); } fn val(&self) -> u32 { match self { SegmentTree::Node(node) => node.value, SegmentTree::Leaf(leaf) => leaf.value, } } fn ind(&self) -> usize { match self { SegmentTree::Node(node) => node.index, SegmentTree::Leaf(leaf) => leaf.index, } } } #[allow(unused_must_use)] #[allow(unused_variables)] fn solve() { let (n, q) = input!(usize, usize); let a = invec!(u32); let mut tree = SegmentTree::new(&a, 0, n - 1); for _ in 0..q { let (op, l, r) = input!(u8, usize, usize); let l = l - 1; let r = r - 1; match op { 1 => { let (_, ltmp) = tree.query(l, l); let (_, rtmp) = tree.query(r, r); (&mut tree).update(l, rtmp); (&mut tree).update(r, ltmp); }, 2 => { println!("{}", tree.query(l, r).0 + 1); }, _ => {}, } } } fn main() { solve(); }