結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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

// 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>>
where
T: FromStr,
{
Ok(self.next()?.parse())
}
pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>
where
T: 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>>
where
F: 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>>>
where
F: 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<()>
where
R: 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(())
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0