Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3608

Problem Lang User Status Time Memory
Static RMQ rust sansen AC 1664 ms 483.51 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
max_random_00 AC 1651 ms 483.33 MiB
max_random_01 AC 1653 ms 483.39 MiB
max_random_02 AC 1658 ms 483.18 MiB
max_random_03 AC 1664 ms 483.51 MiB
max_random_04 AC 1643 ms 483.32 MiB
random_00 AC 1262 ms 372.01 MiB
random_01 AC 1426 ms 445.07 MiB
random_02 AC 480 ms 49.89 MiB
random_03 AC 697 ms 404.33 MiB
random_04 AC 571 ms 254.10 MiB
small_00 AC 5 ms 0.53 MiB
small_01 AC 5 ms 0.62 MiB
small_02 AC 6 ms 0.63 MiB
small_03 AC 4 ms 0.55 MiB
small_04 AC 5 ms 0.63 MiB
small_05 AC 6 ms 0.59 MiB
small_06 AC 7 ms 0.64 MiB
small_07 AC 6 ms 0.59 MiB
small_08 AC 7 ms 0.55 MiB
small_09 AC 4 ms 0.62 MiB

mod persistent_segment_tree { use std::rc::*; pub trait BinaryOperation { type T: Clone; fn fold(l: Self::T, r: Self::T) -> Self::T; fn e() -> Self::T; } type Link<R> = Option<Rc<Node<R>>>; struct Node<R: BinaryOperation> { val: R::T, left: Link<R>, right: Link<R>, } impl<R: BinaryOperation> Node<R> { fn new_node(left: Link<R>, right: Link<R>) -> Link<R> { Some(Rc::new(Node { val: R::fold(Node::get_val(&left), Node::get_val(&right)), left: left, right: right, })) } fn get_val(node: &Link<R>) -> R::T { node.as_ref().map_or(R::e(), |t| t.val.clone()) } fn find(node: &Link<R>, l: usize, r: usize, x: usize, y: usize) -> R::T { if node.is_none() || y <= l || r <= x { return R::e(); } let node = node.as_ref().unwrap(); if x <= l && r <= y { node.val.clone() } else { let m = (l + r) / 2; R::fold(Node::find(&node.left, l, m, x, y), Node::find(&node.right, m, r, x, y)) } } fn update(node: &Link<R>, l: usize, r: usize, x: usize, val: R::T) -> Link<R> { if l + 1 == r { return Some(Rc::new(Node { val: val, left: None, right: None, })); } let mut left = None; let mut right = None; if let Some(node) = node.as_ref() { left = node.left.clone(); right = node.right.clone(); } let m = (l + r) / 2; if x < m { left = Node::update(&left, l, m, x, val); } else { right = Node::update(&right, m, r, x, val); } Node::new_node(left, right) } } pub struct PURQ<R: BinaryOperation> { root: Link<R>, left: usize, right: usize, } impl<R: BinaryOperation> std::clone::Clone for PURQ<R> { fn clone(&self) -> Self { PURQ { root: self.root.clone(), left: self.left, right: self.right, } } } impl<R: BinaryOperation> PURQ<R> { pub fn new(left: usize, right: usize) -> Self { PURQ { root: None, left: left, right: right, } } pub fn update(&self, x: usize, val: R::T) -> Self { assert!(self.left <= x && x < self.right); PURQ { root: Node::update(&self.root, self.left, self.right, x, val), left: self.left, right: self.right, } } pub fn find(&self, l: usize, r: usize) -> R::T { assert!(self.left <= l && l < r && r <= self.right); Node::find(&self.root, self.left, self.right, l, r) } } } use std::io::Read; use std::io::Write; struct R; impl persistent_segment_tree::BinaryOperation for R { type T = u32; fn fold(l: Self::T, r: Self::T) -> Self::T { std::cmp::min(l, r) } fn e() -> Self::T { std::u32::MAX } } fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let q: usize = it.next().unwrap().parse().unwrap(); let mut now = persistent_segment_tree::PURQ::<R>::new(0, n); let mut seg = vec![]; for i in 0..n { let a: u32 = it.next().unwrap().parse().unwrap(); now = now.update(i, a); seg.push(now.clone()); } let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for _ in 0..q { let l: usize = it.next().unwrap().parse().unwrap(); let r: usize = it.next().unwrap().parse().unwrap(); let ans = seg[r - 1].find(l, r); writeln!(out, "{}", ans).ok(); } } fn main() { run(); }