結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:26:22 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,808 ms / 2,500 ms |
コード長 | 17,790 bytes |
コンパイル時間 | 16,685 ms |
コンパイル使用メモリ | 378,764 KB |
実行使用メモリ | 13,896 KB |
最終ジャッジ日時 | 2024-11-16 13:15:11 |
合計ジャッジ時間 | 73,341 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
// The main code is at the very bottom.#[allow(unused_imports)]use {lib::byte::ByteChar,std::cell::{Cell, RefCell},std::cmp::{self,Ordering::{self, *},Reverse,},std::collections::*,std::convert::identity,std::fmt::{self, Debug, Display, Formatter},std::io::prelude::*,std::iter::{self, FromIterator},std::marker::PhantomData,std::mem,std::num::Wrapping,std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},std::process,std::rc::Rc,std::thread,std::time::{Duration, Instant},std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},};#[allow(unused_imports)]#[macro_use]pub mod lib {pub mod byte {pub use self::byte_char::*;mod byte_char {use std::error::Error;use std::fmt::{self, Debug, Display, Formatter};use std::str::FromStr;#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]#[repr(transparent)]pub struct ByteChar(pub u8);impl Debug for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "b'{}'", self.0 as char)}}impl Display for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "{}", self.0 as char)}}impl FromStr for ByteChar {type Err = ParseByteCharError;fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {match s.as_bytes().len() {1 => Ok(ByteChar(s.as_bytes()[0])),0 => Err(ParseByteCharErrorKind::EmptyStr.into()),_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),}}}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]pub struct ParseByteCharError {kind: ParseByteCharErrorKind,}impl Display for ParseByteCharError {fn fmt(&self, f: &mut Formatter) -> fmt::Result {f.write_str(match self.kind {ParseByteCharErrorKind::EmptyStr => "empty string",ParseByteCharErrorKind::TooManyBytes => "too many bytes",})}}impl Error for ParseByteCharError {}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]enum ParseByteCharErrorKind {EmptyStr,TooManyBytes,}impl From<ParseByteCharErrorKind> for ParseByteCharError {fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {ParseByteCharError { kind }}}}}pub mod io {pub use self::scanner::*;mod scanner {use std::io::{self, BufRead};use std::iter;use std::str::FromStr;#[derive(Debug)]pub struct Scanner<R> {reader: R,buf: String,pos: usize,}impl<R: BufRead> Scanner<R> {pub fn new(reader: R) -> Self {Scanner {reader,buf: String::new(),pos: 0,}}pub fn next(&mut self) -> io::Result<&str> {let start = loop {match self.rest().find(|c| c != ' ') {Some(i) => break i,None => self.fill_buf()?,}};self.pos += start;let len = self.rest().find(' ').unwrap_or(self.rest().len());let s = &self.buf[self.pos..][..len]; // self.rest()[..len]self.pos += len;Ok(s)}pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>whereT: FromStr,{Ok(self.next()?.parse())}pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>whereT: FromStr,{iter::repeat_with(|| self.parse_next()).take(n).collect()}pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>whereF: FnMut(u8) -> T,{Ok(self.next()?.bytes().map(&mut f).collect())}pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>whereF: FnMut(u8) -> T,{iter::repeat_with(|| self.map_next_bytes(&mut f)).take(n).collect()}fn rest(&self) -> &str {&self.buf[self.pos..]}fn fill_buf(&mut self) -> io::Result<()> {self.buf.clear();self.pos = 0;let read = self.reader.read_line(&mut self.buf)?;if read == 0 {return Err(io::ErrorKind::UnexpectedEof.into());}if *self.buf.as_bytes().last().unwrap() == b'\n' {self.buf.pop();}Ok(())}}}}}#[allow(dead_code)]mod n91lib_rs {pub mod data_structure {pub mod bit_vector {use crate::n91lib_rs::other::bit::access;use crate::n91lib_rs::other::bit::rank;use crate::n91lib_rs::other::bit::select;use crate::n91lib_rs::other::bit::WORD;use std::iter::FromIterator;use std::iter::IntoIterator;use std::iter::Iterator;pub struct BitVector {data: Box<[Node]>,}struct Node {bit: usize,sum: usize,}impl BitVector {pub fn access(&self, index: usize) -> bool {access(self.data[index / WORD].bit, index % WORD)}pub fn rank0(&self, end: usize) -> usize {end - self.rank1(end)}pub fn rank1(&self, end: usize) -> usize {let t = &self.data[end / WORD];t.sum + rank(t.bit, end % WORD)}pub fn select0(&self, k: usize) -> usize {let (mut st, mut en) = (0, self.data.len());while en - st != 1 {let mid = (st + en) / 2;if mid * WORD - self.data[mid].sum <= k {st = mid;} else {en = mid;}}let rem = k - (st * WORD - self.data[st].sum);st * WORD + select(!self.data[st].bit, rem)}pub fn select1(&self, k: usize) -> usize {let (mut st, mut en) = (0, self.data.len());while en - st != 1 {let mid = (st + en) / 2;if self.data[mid].sum <= k {st = mid;} else {en = mid;}}let rem = k - self.data[st].sum;st * WORD + select(self.data[st].bit, rem)}}impl FromIterator<bool> for BitVector {fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {let mut iter = iter.into_iter();let mut v = Vec::new();let mut sum = 0;'base: loop {let mut bit = 0;for i in 0..WORD {match iter.next() {Some(v) => {if v {bit |= 1 << i;}}None => {v.push(Node { bit: bit, sum: sum });break 'base;}}}v.push(Node { bit: bit, sum: sum });sum += bit.count_ones() as usize;}Self {data: v.into_boxed_slice(),}}}}pub mod wavelet_matrix {use crate::n91lib_rs::data_structure::BitVector;use crate::n91lib_rs::other::bit::access;use std::ops::Range;pub struct WaveletMatrix {data: Box<[(usize, BitVector)]>,}impl WaveletMatrix {pub fn new(bitlen: usize, mut seq: Vec<usize>) -> Self {let len = seq.len();let mut data = Vec::new();for l in (0..bitlen).rev() {let v = seq.iter().map(|&x| access(x, l)).collect::<BitVector>();data.push((v.rank0(len), v));let zeros = seq.iter().filter(|&&x| !access(x, l)).cloned();let ones = seq.iter().filter(|&&x| access(x, l)).cloned();seq = zeros.chain(ones).collect();}Self {data: data.into_iter().rev().collect::<Vec<_>>().into_boxed_slice(),}}pub fn access(&self, mut index: usize) -> usize {let mut ret = 0;for (l, &(z, ref v)) in self.base_iter().rev() {if !v.access(index) {index = v.rank0(index);} else {ret |= 1 << l;index = z + v.rank1(index);}}ret}pub fn rank(&self, value: usize, mut range: Range<usize>) -> usize {for (l, &(z, ref v)) in self.base_iter().rev() {if !access(value, l) {range.start = v.rank0(range.start);range.end = v.rank0(range.end);} else {range.start = z + v.rank1(range.start);range.end = z + v.rank1(range.end);}}range.end - range.start}pub fn select(&self, value: usize, k: usize) -> usize {let mut index = 0;for (l, &(z, ref v)) in self.base_iter().rev() {if !access(value, l) {index = v.rank0(index);} else {index = z + v.rank1(index);}}index += k;for (_, &(z, ref v)) in self.base_iter() {if index < z {index = v.select0(index);} else {index = v.select1(index - z);}}index}pub fn count(&self, idxrng: Range<usize>, valrng: Range<usize>) -> usize {self.count_to(idxrng.clone(), valrng.end) - self.count_to(idxrng, valrng.start)}pub fn quantile(&self, mut range: Range<usize>, mut k: usize) -> usize {let mut ret = 0;for (l, &(z, ref v)) in self.base_iter().rev() {let zeros = v.rank0(range.end) - v.rank0(range.start);if zeros > k {range.start = v.rank0(range.start);range.end = v.rank0(range.end);} else {k -= zeros;ret |= 1 << l;range.start = z + v.rank1(range.start);range.end = z + v.rank1(range.end);}}ret}fn count_to(&self, mut range: Range<usize>, val: usize) -> usize {let mut ret = 0;for (l, &(z, ref v)) in self.base_iter().rev() {if !access(val, l) {range.start = v.rank0(range.start);range.end = v.rank0(range.end);} else {ret += v.rank0(range.end) - v.rank0(range.start);range.start = z + v.rank1(range.start);range.end = z + v.rank1(range.end);}}ret}fn base_iter(&self) -> impl DoubleEndedIterator<Item = (usize, &(usize, BitVector))> {self.data.iter().enumerate()}}}pub use bit_vector::BitVector;}pub mod other {pub mod bit {pub const WORD: usize = (0 as usize).count_zeros() as usize;pub fn access(bit: usize, index: usize) -> bool {bit & 1 << index != 0}pub fn rank(bit: usize, end: usize) -> usize {(bit & !(!0 << end)).count_ones() as usize}#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]pub fn select(bit: usize, k: usize) -> usize {macro_rules! select_impl {($k: expr, $({$b: expr, $m: expr, $s: expr}),*) => {let mut k = $k;let mut r = 0;$(let b = ($b >> r & $m) as usize;if k >= b {k -= b;r += $s;})*r}}#[cfg(target_arch = "x86")]{if is_x86_feature_detected!("bmi2") {use std::arch::x86::_pdep_u32;unsafe { _pdep_u32(1 << k, bit as u32).trailing_zeros() as usize }} else {let b0 = bit as u32;let b1 = (b0 & 0x55555555) + (b0 >> 1 & 0x55555555);let b2 = (b1 & 0x33333333) + (b1 >> 2 & 0x33333333);let b3 = b2 + (b2 >> 4) & 0x0F0F0F0F;let b4 = b3 + (b3 >> 8) & 0x00FF00FF;let b5 = b4 + (b4 >> 16) & 0x0000FFFF;if k >= b5 as usize {return 32;}#[allow(unused_assignments)]{select_impl! {k,{b4, 0xFFFF, 16},{b3, 0xFF, 8},{b2, 0xF, 4},{b1, 0x3, 2},{b0, 0x1, 1}}}}}#[cfg(target_arch = "x86_64")]{if is_x86_feature_detected!("bmi2") {use std::arch::x86_64::_pdep_u64;unsafe { _pdep_u64(1 << k, bit as u64).trailing_zeros() as usize }} else {let b0 = bit as u64;let b1 = (b0 & 0x5555555555555555) + (b0 >> 1 & 0x5555555555555555);let b2 = (b1 & 0x3333333333333333) + (b1 >> 2 & 0x3333333333333333);let b3 = b2 + (b2 >> 4) & 0x0F0F0F0F0F0F0F0F;let b4 = b3 + (b3 >> 8) & 0x00FF00FF00FF00FF;let b5 = b4 + (b4 >> 16) & 0x0000FFFF0000FFFF;let b6 = b5 + (b5 >> 32) & 0x00000000FFFFFFFF;if k >= b6 as usize {return 64;}#[allow(unused_assignments)]{select_impl! {k,{b5, 0xFFFFFFFF, 32},{b4, 0xFFFF, 16},{b3, 0xFF, 8},{b2, 0xF, 4},{b1, 0x3, 2},{b0, 0x1, 1}}}}}}pub fn bsf(bit: usize) -> usize {assert_ne!(bit, 0);bit.trailing_zeros() as usize}pub fn bsr(bit: usize) -> usize {assert_ne!(bit, 0);WORD - 1 - bit.leading_zeros() as usize}pub fn ceil_log2(n: usize) -> usize {assert_ne!(n, 0);WORD - 1 - (2 * n - 1).leading_zeros() as usize}}}}#[allow(unused_macros)]macro_rules! eprint {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprint!($($arg)*)}};}#[allow(unused_macros)]macro_rules! eprintln {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprintln!($($arg)*)}};}#[allow(unused_macros)]macro_rules! dbg {($($arg:tt)*) => {if cfg!(debug_assertions) {std::dbg!($($arg)*)} else {($($arg)*)}};}const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);const INTERACTIVE: bool = false;fn main() -> std::io::Result<()> {match CUSTOM_STACK_SIZE_MIB {Some(stack_size_mib) => std::thread::Builder::new().name("run_solver".to_owned()).stack_size(stack_size_mib * 1024 * 1024).spawn(run_solver)?.join().unwrap(),None => run_solver(),}}fn run_solver() -> std::io::Result<()> {let stdin = std::io::stdin();let reader = stdin.lock();let stdout = std::io::stdout();let writer = stdout.lock();macro_rules! with_wrapper {($($wrapper:expr)?) => {{let mut writer = $($wrapper)?(writer);solve(reader, &mut writer)?;writer.flush()}};}if cfg!(debug_assertions) || INTERACTIVE {with_wrapper!()} else {with_wrapper!(std::io::BufWriter::new)}}fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>whereR: BufRead,W: Write,{let mut _scanner = lib::io::Scanner::new(reader);#[allow(unused_macros)]macro_rules! scan {($T:ty) => {_scanner.parse_next::<$T>()?.unwrap()};($($T:ty),+) => {($(scan!($T)),+)};($T:ty; $n:expr) => {_scanner.parse_next_n::<$T>($n)?.unwrap()};($($T:ty),+; $n:expr) => {iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) }).take($n).collect::<std::io::Result<Vec<_>>>()?};}#[allow(unused_macros)]macro_rules! scan_bytes_map {($f:expr) => {_scanner.map_next_bytes($f)?};($f:expr; $n:expr) => {_scanner.map_next_bytes_n($n, $f)?};}#[allow(unused_macros)]macro_rules! print {($($arg:tt)*) => {write!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! println {($($arg:tt)*) => {writeln!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! answer {($($arg:tt)*) => {{println!($($arg)*);return Ok(());}};}{use n91lib_rs::data_structure::wavelet_matrix::WaveletMatrix;fn dist(x: usize, y: usize) -> usize {if x > y {x - y} else {y - x}}let n = scan!(usize);let x = scan!(usize; n);let wm = WaveletMatrix::new(30, x);let q = scan!(usize);for _ in 0..q {let (l, r, x) = scan!(usize, usize, usize);let (l, r) = (l - 1, r - 1);let nth = |i| wm.quantile(l..r + 1, i);let mut ok = 0;let mut ng = n;while ng - ok > 1 {let mid = (ok + ng) / 2;if nth(mid) <= x {ok = mid;} else {ng = mid;}}let mut ans = dist(x, nth(ok));if ok + 1 < r - l + 1 {ans = ans.min(dist(x, nth(ok + 1)));}println!("{}", ans);}}#[allow(unreachable_code)]Ok(())}