Submit Info #21148

Problem Lang User Status Time Memory
Static RMQ rust (anonymous) AC 416 ms 50.22 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.61 MiB
max_random_00 AC 399 ms 48.65 MiB
max_random_01 AC 400 ms 48.72 MiB
max_random_02 AC 410 ms 48.47 MiB
max_random_03 AC 399 ms 48.78 MiB
max_random_04 AC 399 ms 48.65 MiB
random_00 AC 325 ms 37.96 MiB
random_01 AC 332 ms 44.09 MiB
random_02 AC 254 ms 10.61 MiB
random_03 AC 68 ms 34.36 MiB
random_04 AC 102 ms 23.11 MiB
small_00 AC 2 ms 0.61 MiB
small_01 AC 2 ms 0.61 MiB
small_02 AC 1 ms 0.64 MiB
small_03 AC 2 ms 0.62 MiB
small_04 AC 1 ms 0.66 MiB
small_05 AC 1 ms 0.59 MiB
small_06 AC 1 ms 0.57 MiB
small_07 AC 0 ms 0.62 MiB
small_08 AC 2 ms 0.61 MiB
small_09 AC 1 ms 0.62 MiB
small_width_query_00 AC 412 ms 50.10 MiB
small_width_query_01 AC 411 ms 50.16 MiB
small_width_query_02 AC 416 ms 50.15 MiB
small_width_query_03 AC 413 ms 50.22 MiB
small_width_query_04 AC 411 ms 50.15 MiB

fn main() { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let mut s = s.split_whitespace(); let n: usize = s.next().unwrap().parse().unwrap(); let q: usize = s.next().unwrap().parse().unwrap(); let a: Vec<i32> = s.by_ref().take(n).map(|a| a.parse().unwrap()).collect(); let st = SparseTable::new(a, |a, b| std::cmp::min(a, b)); use std::io::Write; let out = std::io::stdout(); let mut out = out.lock(); for _ in 0..q { let l: usize = s.next().unwrap().parse().unwrap(); let r: usize = s.next().unwrap().parse().unwrap(); writeln!(out, "{}", st.fold(l, r).unwrap()).unwrap(); } } pub struct SparseTable<T, F> { data: Vec<T>, indices: Vec<usize>, n: usize, op: F, } impl<T, F> SparseTable<T, F> where T: Clone + std::fmt::Debug, F: Fn(T, T) -> T, { pub fn new(src: Vec<T>, op: F) -> Self { let n = src.len(); let log2 = (n + 1).next_power_of_two().trailing_zeros() - 1; let mut indices = vec![0]; let mut data = src; for k in 1..=log2 as usize { indices.push(data.len()); for i in 0..=n - (1 << k) { data.push(op( data[indices[k - 1] + i].clone(), data[indices[k - 1] + i + (1 << (k - 1))].clone(), )); } } Self { data, indices, n, op, } } pub fn fold(&self, l: usize, r: usize) -> Option<T> { if l >= r || r > self.n { None } else { let i = (r - l + 1).next_power_of_two().trailing_zeros() - 1; let i = i as usize; Some((self.op)( self.data[self.indices[i] + l].clone(), self.data[self.indices[i] + r - (1 << i)].clone(), )) } } }