結果
問題 | No.1332 Range Nearest Query |
ユーザー |
|
提出日時 | 2021-01-08 23:46:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 645 ms / 2,500 ms |
コード長 | 8,400 bytes |
コンパイル時間 | 15,850 ms |
コンパイル使用メモリ | 376,772 KB |
実行使用メモリ | 64,356 KB |
最終ジャッジ日時 | 2024-11-16 18:46:10 |
合計ジャッジ時間 | 37,898 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#![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/monoidpub trait Monoid: std::ops::Mul<Output = Self>whereSelf: 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 leaveslength_upper: usize, // power of 2size: usize, // of nodesdata: 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();}