結果
問題 | No.1332 Range Nearest Query |
ユーザー | cympfh |
提出日時 | 2021-01-08 23:46:29 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 513 ms / 2,500 ms |
コード長 | 8,400 bytes |
コンパイル時間 | 12,400 ms |
コンパイル使用メモリ | 377,188 KB |
実行使用メモリ | 64,476 KB |
最終ジャッジ日時 | 2024-04-28 06:00:40 |
合計ジャッジ時間 | 33,451 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 448 ms
40,344 KB |
testcase_04 | AC | 444 ms
40,332 KB |
testcase_05 | AC | 462 ms
40,340 KB |
testcase_06 | AC | 413 ms
64,348 KB |
testcase_07 | AC | 416 ms
64,352 KB |
testcase_08 | AC | 452 ms
64,352 KB |
testcase_09 | AC | 418 ms
64,348 KB |
testcase_10 | AC | 410 ms
64,348 KB |
testcase_11 | AC | 411 ms
64,356 KB |
testcase_12 | AC | 409 ms
64,352 KB |
testcase_13 | AC | 417 ms
64,352 KB |
testcase_14 | AC | 398 ms
64,352 KB |
testcase_15 | AC | 393 ms
64,476 KB |
testcase_16 | AC | 502 ms
64,352 KB |
testcase_17 | AC | 513 ms
64,352 KB |
testcase_18 | AC | 507 ms
64,352 KB |
testcase_19 | AC | 492 ms
64,356 KB |
testcase_20 | AC | 493 ms
64,268 KB |
testcase_21 | AC | 495 ms
64,352 KB |
testcase_22 | AC | 508 ms
64,352 KB |
testcase_23 | AC | 498 ms
64,368 KB |
testcase_24 | AC | 490 ms
64,224 KB |
testcase_25 | AC | 509 ms
64,352 KB |
testcase_26 | AC | 312 ms
64,224 KB |
testcase_27 | AC | 314 ms
64,356 KB |
testcase_28 | AC | 168 ms
8,960 KB |
testcase_29 | AC | 170 ms
9,264 KB |
testcase_30 | AC | 166 ms
9,088 KB |
testcase_31 | AC | 159 ms
8,960 KB |
testcase_32 | AC | 166 ms
8,960 KB |
testcase_33 | AC | 166 ms
9,008 KB |
testcase_34 | AC | 154 ms
8,960 KB |
testcase_35 | AC | 158 ms
9,088 KB |
testcase_36 | AC | 165 ms
8,960 KB |
testcase_37 | AC | 171 ms
9,276 KB |
testcase_38 | AC | 373 ms
36,080 KB |
testcase_39 | AC | 230 ms
10,112 KB |
testcase_40 | AC | 495 ms
64,112 KB |
testcase_41 | AC | 282 ms
15,068 KB |
testcase_42 | AC | 357 ms
35,756 KB |
testcase_43 | AC | 314 ms
25,756 KB |
testcase_44 | AC | 416 ms
38,908 KB |
testcase_45 | AC | 406 ms
37,916 KB |
testcase_46 | AC | 362 ms
23,776 KB |
testcase_47 | AC | 386 ms
37,012 KB |
ソースコード
#![allow(unused_imports, unused_macros, dead_code)] use std::cmp::*; use std::collections::*; macro_rules! min { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| min!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = min!($($ys),*); if $x < t { $x } else { t } }} } macro_rules! max { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| max!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = max!($($ys),*); if $x > t { $x } else { t } }} } macro_rules! trace { ($x:expr) => { #[cfg(debug_assertions)] eprintln!(">>> {} = {:?}", stringify!($x), $x) }; ($($xs:expr),*) => { trace!(($($xs),*)) } } macro_rules! put { (.. $x:expr) => {{ let mut it = $x.iter(); if let Some(x) = it.next() { print!("{}", x); } for x in it { print!(" {}", x); } println!(""); }}; ($x:expr) => { println!("{}", $x) }; ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) } } const M: i64 = 1_000_000_007; #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] enum Item { Elem(usize, i64), Query(usize, usize, usize, i64), } fn main() { let mut sc = Scanner::new(); use Item::*; let mut items = vec![]; let n: usize = sc.cin(); for i in 0..n { let x: i64 = sc.cin(); items.push(Elem(i, x)); } let q: usize = sc.cin(); for i in 0..q { let l = sc.cin::<usize>() - 1; let r = sc.cin::<usize>() - 1; let x: i64 = sc.cin(); items.push(Query(i, l, r, x)); } let mut ans = vec![MinInt::Maximal; q]; items.sort_by_key(|item| match item { Elem(_, x) => 2 * x, Query(_, _, _, x) => 2 * x + 1, }); trace!(&items); let mut st = RMaxQ::new(n); for &item in items.iter() { match item { Elem(i, x) => { st.update(i, MaxInt::Val(x)); } Query(i, l, r, x) => match st.product(l..r + 1) { MaxInt::Val(m) => { ans[i] = min!(ans[i], MinInt::Val(x - m)); trace!(i, ans[i]); } _ => {} }, } } items.sort_by_key(|item| match item { Elem(_, x) => -2 * x, Query(_, _, _, x) => -2 * x + 1, }); trace!(&items); let mut st = RMinQ::new(n); for &item in items.iter() { match item { Elem(i, x) => { st.update(i, MinInt::Val(x)); } Query(i, l, r, x) => match st.product(l..r + 1) { MinInt::Val(m) => { ans[i] = min!(ans[i], MinInt::Val(m - x)); trace!(i, ans[i]); } _ => {} }, } } for i in 0..q { put!(ans[i].unwrap()); } } // @sequence/tree/rmq // @algebra/monoid_minmax // @algebra/monoid pub trait Monoid: std::ops::Mul<Output = Self> where Self: std::marker::Sized, { fn unit() -> Self; } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Sum(pub i64); impl std::ops::Mul for Sum { type Output = Self; fn mul(self, other: Self) -> Self { Self(self.0 + other.0) } } impl Monoid for Sum { fn unit() -> Self { Self(0) } } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Prod(pub i64); impl std::ops::Mul for Prod { type Output = Self; fn mul(self, other: Self) -> Self { Self(self.0 * other.0) } } impl Monoid for Prod { fn unit() -> Self { Self(1) } } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub enum MaxInt<X> { Minimal, Val(X), } impl<X> MaxInt<X> { pub fn unwrap(self) -> X { if let Self::Val(x) = self { x } else { panic!() } } } impl<X: Ord> std::ops::Mul for MaxInt<X> { type Output = Self; fn mul(self, other: Self) -> Self { if self > other { self } else { other } } } impl<X: Ord + Copy> Monoid for MaxInt<X> { fn unit() -> Self { MaxInt::Minimal } } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub enum MinInt<X> { Val(X), Maximal, } impl<X> MinInt<X> { pub fn unwrap(self) -> X { if let Self::Val(x) = self { x } else { panic!(); } } } impl<X: Ord> std::ops::Mul for MinInt<X> { type Output = Self; fn mul(self, other: Self) -> Self { if self < other { self } else { other } } } impl<X: Ord + Copy> Monoid for MinInt<X> { fn unit() -> Self { MinInt::Maximal } } // @sequence/tree/segment_tree #[derive(Debug, Clone)] pub struct SegmentTree<X> { length: usize, // of leaves length_upper: usize, // power of 2 size: usize, // of nodes data: Vec<X>, } impl<X> std::ops::Index<usize> for SegmentTree<X> { type Output = X; fn index(&self, i: usize) -> &Self::Output { &self.data[self.size / 2 + i] } } impl<X: Copy + Monoid> SegmentTree<X> { pub fn new(length: usize) -> Self { let mut length_upper = 1; while length_upper < length { length_upper *= 2; } let size = length_upper * 2 - 1; let data = vec![X::unit(); size]; SegmentTree { length, length_upper, size, data, } } pub fn from(xs: Vec<X>) -> Self { let mut tree = Self::new(xs.len()); for i in 0..xs.len() { tree.data[tree.size / 2 + i] = xs[i]; } for i in (0..tree.size / 2).rev() { tree.data[i] = tree.data[2 * i + 1] * tree.data[2 * i + 2]; } tree } pub fn to_vec(self) -> Vec<X> { self.data[self.size / 2..].to_vec() } pub fn update(&mut self, i: usize, t: X) { let mut u = self.size / 2 + i; self.data[u] = t; while u > 0 { u = (u - 1) / 2; self.data[u] = self.data[u * 2 + 1] * self.data[u * 2 + 2]; } } fn product_sub( &self, range: std::ops::Range<usize>, u: usize, focus: std::ops::Range<usize>, ) -> X { if focus.end <= range.start || range.end <= focus.start { X::unit() } else if range.start <= focus.start && focus.end <= range.end { self.data[u] } else { let mid = (focus.start + focus.end) / 2; let a = self.product_sub(range.clone(), u * 2 + 1, focus.start..mid); let b = self.product_sub(range.clone(), u * 2 + 2, mid..focus.end); a * b } } pub fn product(&self, range: std::ops::Range<usize>) -> X { self.product_sub(range, 0, 0..self.length_upper) } } impl<X: std::fmt::Debug> SegmentTree<X> { pub fn debug(&self) { #[cfg(debug_assertions)] for i in 0..self.size { if i > 0 && (i + 1).count_ones() == 1 { eprintln!(); } eprint!("{:?} ", &self.data[i]); } eprintln!(); } } pub type RMaxQ<X> = SegmentTree<MaxInt<X>>; pub type RMinQ<X> = SegmentTree<MinInt<X>>; use std::collections::VecDeque; use std::io::{self, Write}; use std::str::FromStr; struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, } impl Scanner { fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new(), } } fn cin<T: FromStr>(&mut self) -> T { while self.buffer.is_empty() { let mut line = String::new(); let _ = self.stdin.read_line(&mut line); for w in line.split_whitespace() { self.buffer.push_back(String::from(w)); } } self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap() } fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() } fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() } } fn flush() { std::io::stdout().flush().unwrap(); }