#617894 (Rust) No.1332 Range Nearest Query

提出ソース

結果

問題	No.1332 Range Nearest Query
ユーザー	nebocco
提出日時	2021-02-14 15:44:10
言語	Rust (1.77.0)
結果	TLE
実行時間	-
コード長	9,791 bytes
コンパイル時間	1,321 ms
コンパイル使用メモリ	165,224 KB
実行使用メモリ	22,544 KB
最終ジャッジ日時	2023-09-29 05:58:07
合計ジャッジ時間	7,300 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 8,756 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

fn main() {
	let mut io = IO::new();
	let n = io.scan();
	let sq = 700;
	let lis = io.scan_vec::<i64>(n);
	let q = io.scan();
	let mut query = io.scan_vec::<(usize, usize, i64)>(q).into_iter().enumerate().collect::<Vec<_>>();
	query.sort_by_key(|&(_, (l, r, _))| {
		(l / sq + 1) * 2_000_000 + if l / sq & 1 == 0 {
			r
		} else {
			n - r
		}
	});
	let mut ans = vec![0; q];
	let mut sl = SquareSkipList::new();
	let mut cl = 0;
	let mut cr = 0;
	for &(idx, (l, r, x)) in &query {
		for i in l-1..cl {
			sl.push(lis[i]);
			// io.println(("l push", lis[i]));
		}
		for i in cr..r {
			sl.push(lis[i]);
			// io.println(("r push", lis[i]));
		}
		for i in cl..l-1 {
			sl.remove(lis[i]).ok();
			// io.println(("l remove", lis[i]));
		}
		for i in r..cr {
			sl.remove(lis[i]).ok();
			// io.println(("r remove", lis[i]));
		}
		let hi = sl.search_higher_equal(x).unwrap_or(10i64.pow(15));
		let lo = sl.search_lower_equal(x).unwrap_or(-10i64.pow(15));
		ans[idx] = std::cmp::min(hi - x, x - lo);
		// io.println(format!("query {}: {}", idx, ans[idx]));
		cl = l-1;
		cr = r;
	}
	io.iterln(ans.into_iter(), "\n")
}

// ------------ Square Skip List start ------------
struct XorShift(i64);

impl XorShift {
	fn new(seed: i64) -> Self {
		Self(seed)
	}

	fn next(&mut self) -> i64 {
		self.0 ^= (self.0 & 0x7ffff) << 13;
		self.0 ^= self.0 >> 17;
		self.0 ^= (self.0 & 0x7ffffff) << 5;
		self.0
	}
}

pub struct SquareSkipList {
	square: i64,
	layer0: Vec<Box<Vec<i64>>>,
	layer1: Vec<i64>,
	rand: XorShift,
}

impl SquareSkipList {
	pub fn new() -> Self {
		let square = 1000;
		let layer0 = vec![Box::new(Vec::new())];
		let layer1 = vec![std::i64::MAX];
		let rand = XorShift::new(42);
		Self{ square, layer0, layer1, rand }
	}

	pub fn push(&mut self, x: i64) {
		let idx1 = self.layer1.binary_search(&x).unwrap_or_else(|s| s);
		let idx0 = self.layer0[idx1].binary_search(&x).unwrap_or_else(|s| s);
		if self.rand.next() % self.square == 0 {
			self.layer1.insert(idx1, x);
			let vec1 = self.layer0[idx1].split_off(idx0);
			self.layer0.insert(idx1+1, Box::new(vec1));
		} else {
			self.layer0[idx1].insert(idx0, x);
		}
	}

	// if x not in list ...
	pub fn remove(&mut self, x: i64) -> Result<(), ()> {
		let idx1 = self.layer1.binary_search(&x).unwrap_or_else(|s| s);
		let idx0 = self.layer0[idx1].binary_search(&x).unwrap_or_else(|s| s);
		if idx0 == self.layer0[idx1].len() {
			if self.layer1[idx1] == x {
				let mut vec1 = self.layer0.remove(idx1+1);
				self.layer0[idx1].append(&mut vec1);
				self.layer1.remove(idx1);
				Ok(())
			} else {
				Err(())
			}
		} else {
			if self.layer0[idx1][idx0] == x {
				self.layer0[idx1].remove(idx0);
				Ok(())
			} else {
				Err(())
			}
		}
	}

	pub fn search_higher_equal(&self, x: i64) -> Option<i64> {
		let idx1 = self.layer1.binary_search(&x);
		if idx1.is_ok() { return Some(x); }
		let idx1 = idx1.unwrap_err();
		if idx1 == self.layer1.len() { return None; }
		let idx0 = self.layer0[idx1].binary_search(&x);
		if idx0.is_ok() { return Some(x); }
		let idx0 = idx0.unwrap_err();
		if idx0 == self.layer0[idx1].len() {
			if idx1 == self.layer1.len() - 1 { return None; }
			Some(self.layer1[idx1])
		} else {
			Some(self.layer0[idx1][idx0])
		}
	}

	pub fn search_lower_equal(&self, x: i64) -> Option<i64> {
		let idx1 = self.layer1.binary_search(&x);
		if idx1.is_ok() { return Some(x); }
		let idx1 = idx1.unwrap_err();
		let idx0 = self.layer0[idx1].binary_search(&x);
		if idx0.is_ok() { return Some(x); }
		let idx0 = idx0.unwrap_err();
		if idx0 == 0 {
			if idx1 == 0 {
				None
			} else {
				Some(self.layer1[idx1-1])
			}
		} else {
			Some(self.layer0[idx1][idx0-1])
		}
	}

	pub fn pop(&mut self, idx: usize) -> i64 {
		let mut s = 0;
		let mut li = self.layer1.len();
		for (i, e) in self.layer0.iter().enumerate() {
			s += e.len() + 1;
			if s > idx { li = i; break; }
		}
		if s == idx + 1 {
			let mut vec1 = self.layer0.remove(li+1);
			self.layer0[li].append(&mut vec1);
			self.layer1.remove(li)
		} else {
			let i = idx + self.layer0[li].len() - s;
			self.layer0[li].remove(i)
		}
	}
}
// ------------ Square Skip List end ------------

// ------------ algebraic traits start ------------
use std::marker::Sized;
use std::ops::*;

/// 元
pub trait Element: Sized + Clone + PartialEq {}
impl<T: Sized + Clone + PartialEq> Element for T {}

/// 結合性
pub trait Associative: Magma {}

/// マグマ
pub trait Magma: Element + Add<Output=Self> {}
impl<T: Element + Add<Output=Self>> Magma for T {}

/// 半群
pub trait SemiGroup: Magma + Associative {}
impl<T: Magma + Associative> SemiGroup for T {}

/// モノイド
pub trait Monoid: SemiGroup + Zero {}
impl<T: SemiGroup + Zero> Monoid for T {}

pub trait ComMonoid: Monoid + AddAssign {}
impl<T: Monoid + AddAssign> ComMonoid for T {}

/// 群
pub trait Group: Monoid + Neg<Output=Self> {}
impl<T: Monoid + Neg<Output=Self>> Group for T {}

pub trait ComGroup: Group + ComMonoid {}
impl<T: Group + ComMonoid> ComGroup for T {}

/// 半環
pub trait SemiRing: ComMonoid + Mul<Output=Self> + One {}
impl<T: ComMonoid + Mul<Output=Self> + One> SemiRing for T {}

/// 環
pub trait Ring: ComGroup + SemiRing {}
impl<T: ComGroup + SemiRing> Ring for T {}

pub trait ComRing: Ring + MulAssign {}
impl<T: Ring + MulAssign> ComRing for T {}

/// 体
pub trait Field: ComRing + Div<Output=Self> + DivAssign {}
impl<T: ComRing + Div<Output=Self> + DivAssign> Field for T {}

/// 加法単元
pub trait Zero: Element {
    fn zero() -> Self;
    fn is_zero(&self) -> bool {
        *self == Self::zero()
    }
}

/// 乗法単元
pub trait One: Element {
    fn one() -> Self;
    fn is_one(&self) -> bool {
        *self == Self::one()
    }
}

macro_rules! impl_integer {
    ($($T:ty,)*) => {
        $(
            impl Associative for $T {}

            impl Zero for $T {
                fn zero() -> Self { 0 }
                fn is_zero(&self) -> bool { *self == 0 }
            }

            impl<'a> Zero for &'a $T {
                fn zero() -> Self { &0 }
                fn is_zero(&self) -> bool { *self == &0 }
            }

            impl One for $T {
                fn one() -> Self { 1 }
                fn is_one(&self) -> bool { *self == 1 }
            }

            impl<'a> One for &'a $T {
                fn one() -> Self { &1 }
                fn is_one(&self) -> bool { *self == &1 }
            }
        )*
    };
}

impl_integer! {
    i8, i16, i32, i64, i128, isize,
    u8, u16, u32, u64, u128, usize,
}
// ------------ algebraic traits end ------------

// ------------ io module start ------------

use std::io::{stdout, BufWriter, Read, StdoutLock, Write};

pub struct IO {
	iter: std::str::SplitAsciiWhitespace<'static>,
	buf: BufWriter<StdoutLock<'static>>,
}

impl IO {
	pub fn new() -> Self {
		let mut input = String::new();
		std::io::stdin().read_to_string(&mut input).unwrap();
		let input = Box::leak(input.into_boxed_str());
		let out = Box::new(stdout());
		IO {
			iter: input.split_ascii_whitespace(),
			buf: BufWriter::new(Box::leak(out).lock()),
		}
	}
	fn scan_str(&mut self) -> &'static str {
		self.iter.next().unwrap()
	}
	fn scan_raw(&mut self) -> &'static [u8] {
		self.scan_str().as_bytes()
	}
	pub fn scan<T: Scan>(&mut self) -> T {
		T::scan(self)
	}
	pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<T> {
		(0..n).map(|_| self.scan()).collect()
	}
}

impl IO {
	pub fn print<T: Print>(&mut self, x: T) {
		T::print(self, x);
	}
	pub fn println<T: Print>(&mut self, x: T) {
		self.print(x);
		self.print("\n");
	}
	pub fn iterln<T: Print, I: Iterator<Item = T>>(&mut self, mut iter: I, delim: &str) {
		if let Some(v) = iter.next() {
			self.print(v);
			for v in iter {
				self.print(delim);
				self.print(v);
			}
		}
		self.print("\n");
	}
	pub fn flush(&mut self) {
		self.buf.flush().unwrap();
	}
}

impl Default for IO {
	fn default() -> Self {
		Self::new()
	}
}

pub trait Scan {
	fn scan(io: &mut IO) -> Self;
}

macro_rules! impl_parse_int {
	($($t:tt),*) => {
		$(
			impl Scan for $t {
				fn scan(s: &mut IO) -> Self {
					let mut res = 0;
					let mut neg = false;
					for d in s.scan_raw() {
						if *d == b'-' {
							neg = true;
						} else {
							res *= 10;
							res += (*d - b'0') as $t;
						}
					}
					if neg { res = res.wrapping_neg(); }
					res
				}
			}
		)*
	};
}

impl_parse_int!(i16, i32, i64, isize, u16, u32, u64, usize);

impl<T: Scan, U: Scan> Scan for (T, U) {
	fn scan(s: &mut IO) -> Self {
		(T::scan(s), U::scan(s))
	}
}

impl<T: Scan, U: Scan, V: Scan> Scan for (T, U, V) {
	fn scan(s: &mut IO) -> Self {
		(T::scan(s), U::scan(s), V::scan(s))
	}
}

impl<T: Scan, U: Scan, V: Scan, W: Scan> Scan for (T, U, V, W) {
	fn scan(s: &mut IO) -> Self {
		(T::scan(s), U::scan(s), V::scan(s), W::scan(s))
	}
}

pub trait Print {
	fn print(w: &mut IO, x: Self);
}

macro_rules! impl_print_int {
	($($t:ty),*) => {
		$(
			impl Print for $t {
				fn print(w: &mut IO, x: Self) {
					w.buf.write_all(x.to_string().as_bytes()).unwrap();
				}
			}
		)*
	};
}

impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize);

impl Print for u8 {
	fn print(w: &mut IO, x: Self) {
		w.buf.write_all(&[x]).unwrap();
	}
}

impl Print for &[u8] {
	fn print(w: &mut IO, x: Self) {
		w.buf.write_all(x).unwrap();
	}
}

impl Print for &str {
	fn print(w: &mut IO, x: Self) {
		w.print(x.as_bytes());
	}
}

impl Print for String {
	fn print(w: &mut IO, x: Self) {
		w.print(x.as_bytes());
	}
}

impl<T: Print, U: Print> Print for (T, U) {
	fn print(w: &mut IO, (x, y): Self) {
		w.print(x);
		w.print(" ");
		w.print(y);
	}
}

impl<T: Print, U: Print, V: Print> Print for (T, U, V) {
	fn print(w: &mut IO, (x, y, z): Self) {
		w.print(x);
		w.print(" ");
		w.print(y);
		w.print(" ");
		w.print(z);
	}
}

// ------------ io module end ------------

yukicoder

結果

テストケース

ソースコード