結果

問題 No.1332 Range Nearest Query
ユーザー cympfhcympfh
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0