結果
| 問題 | No.871 かえるのうた |
| ユーザー |
 へのく
|
| 提出日時 | 2020-06-25 10:46:52 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 85 ms / 2,000 ms |
| コード長 | 31,321 bytes |
| コンパイル時間 | 15,753 ms |
| コンパイル使用メモリ | 382,324 KB |
| 実行使用メモリ | 10,520 KB |
| 最終ジャッジ日時 | 2024-05-07 16:39:46 |
| 合計ジャッジ時間 | 16,335 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 0 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 1 ms
5,376 KB |
| testcase_04 | AC | 1 ms
5,376 KB |
| testcase_05 | AC | 1 ms
5,376 KB |
| testcase_06 | AC | 1 ms
5,376 KB |
| testcase_07 | AC | 1 ms
5,376 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | AC | 1 ms
5,376 KB |
| testcase_11 | AC | 1 ms
5,376 KB |
| testcase_12 | AC | 9 ms
5,376 KB |
| testcase_13 | AC | 2 ms
5,376 KB |
| testcase_14 | AC | 57 ms
10,264 KB |
| testcase_15 | AC | 55 ms
10,256 KB |
| testcase_16 | AC | 82 ms
10,520 KB |
| testcase_17 | AC | 51 ms
9,908 KB |
| testcase_18 | AC | 10 ms
5,376 KB |
| testcase_19 | AC | 58 ms
10,264 KB |
| testcase_20 | AC | 6 ms
5,376 KB |
| testcase_21 | AC | 25 ms
5,496 KB |
| testcase_22 | AC | 1 ms
5,376 KB |
| testcase_23 | AC | 1 ms
5,376 KB |
| testcase_24 | AC | 1 ms
5,376 KB |
| testcase_25 | AC | 2 ms
5,376 KB |
| testcase_26 | AC | 8 ms
5,376 KB |
| testcase_27 | AC | 7 ms
5,376 KB |
| testcase_28 | AC | 1 ms
5,376 KB |
| testcase_29 | AC | 26 ms
8,096 KB |
| testcase_30 | AC | 59 ms
8,720 KB |
| testcase_31 | AC | 1 ms
5,376 KB |
| testcase_32 | AC | 55 ms
8,216 KB |
| testcase_33 | AC | 44 ms
10,276 KB |
| testcase_34 | AC | 12 ms
5,376 KB |
| testcase_35 | AC | 28 ms
7,884 KB |
| testcase_36 | AC | 36 ms
9,236 KB |
| testcase_37 | AC | 33 ms
5,712 KB |
| testcase_38 | AC | 85 ms
9,912 KB |
| testcase_39 | AC | 75 ms
9,724 KB |
| testcase_40 | AC | 44 ms
8,240 KB |
| testcase_41 | AC | 1 ms
5,376 KB |
| testcase_42 | AC | 38 ms
8,884 KB |
| testcase_43 | AC | 1 ms
5,376 KB |
| testcase_44 | AC | 1 ms
5,376 KB |
| testcase_45 | AC | 2 ms
5,376 KB |
| testcase_46 | AC | 1 ms
5,376 KB |
| testcase_47 | AC | 0 ms
5,376 KB |
| testcase_48 | AC | 0 ms
5,376 KB |
コンパイルメッセージ
warning: unused return value of `std::mem::replace` that must be used
--> src/main.rs:621:13
|
621 | std::mem::replace(tree, new_tree);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: if you don't need the old value, you can just assign the new value directly
= note: `#[warn(unused_must_use)]` on by default
help: use `let _ = ...` to ignore the resulting value
|
621 | let _ = std::mem::replace(tree, new_tree);
| +++++++
ソースコード
#![allow(unused_imports, non_snake_case)]
#![allow(dead_code)]
use crate::scanner::Scanner;
use crate::{arraylist::List, data_structure::treap::TreapSet};
use std::collections::HashMap;
fn main() {
let mut scan = Scanner::new();
let n = scan.read::<i32>();
let k = scan.read::<i32>() - 1;
let x = scan.readn::<i64>(n);
let a = scan.readn::<i64>(n);
let xi = x.enumerate().map(|t| (t.1, t.0)).to::<HashMap<_, _>>();
let mut set = x.to::<TreapSet<_>>();
let mut stack = list!();
let mut cnt = 1;
stack.push(x[k]);
set.remove(&x[k]);
while let Some(z) = stack.pop() {
let i = xi[&z];
for key in set.range(z - a[i]..z + a[i] + 1) {
stack.push(*key);
cnt += 1;
}
set.erase(z - a[i]..z + a[i] + 1);
}
println!("{}", cnt);
}
pub mod independent {
pub mod integer {
pub trait Int:
std::ops::Add<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::ops::AddAssign
+ std::ops::SubAssign
+ std::ops::MulAssign
+ std::ops::DivAssign
+ std::hash::Hash
+ PartialEq
+ Eq
+ PartialOrd
+ Ord
+ Copy
{
fn to_u8(&self) -> u8;
fn to_u16(&self) -> u16;
fn to_u32(&self) -> u32;
fn to_u64(&self) -> u64;
fn to_u128(&self) -> u128;
fn to_i8(&self) -> i8;
fn to_i16(&self) -> i16;
fn to_i32(&self) -> i32;
fn to_i64(&self) -> i64;
fn to_i128(&self) -> i128;
fn to_usize(&self) -> usize;
fn to_isize(&self) -> isize;
fn from_u8(x: u8) -> Self;
fn from_u16(x: u16) -> Self;
fn from_u32(x: u32) -> Self;
fn from_u64(x: u64) -> Self;
fn from_u128(x: u128) -> Self;
fn from_i8(x: i8) -> Self;
fn from_i16(x: i16) -> Self;
fn from_i32(x: i32) -> Self;
fn from_i64(x: i64) -> Self;
fn from_i128(x: i128) -> Self;
fn from_usize(x: usize) -> Self;
fn from_isize(x: isize) -> Self;
fn zero() -> Self;
fn one() -> Self;
fn next(&self) -> Self {
*self + Self::one()
}
}
macro_rules ! impl_integer_functions { ( $ selftpe : ident , $ ( $ tofn : ident , $ fromfn : ident , $ tpe : ident ) ,* ) => { $ ( fn $ tofn ( & self ) -> $ tpe { * self as $ tpe } fn $ fromfn ( x : $ tpe ) -> Self { x as $ selftpe } ) * } ; }
macro_rules ! impl_integer { ( $ ( $ tpe : ident ) ,* ) => { $ ( impl Int for $ tpe { impl_integer_functions ! ( $ tpe , to_u8 , from_u8 , u8 , to_u16 , from_u16 , u16 , to_u32 , from_u32 , u32 , to_u64 , from_u64 , u64 , to_u128 , from_u128 , u128 , to_i8 , from_i8 , i8 , to_i16 , from_i16 , i16 , to_i32 , from_i32 , i32 , to_i64 , from_i64 , i64 , to_i128 , from_i128 , i128 , to_usize , from_usize , usize , to_isize , from_isize , isize ) ; fn zero ( ) -> Self { 0 } fn one ( ) -> Self { 1 } } ) * } ; }
impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
}
pub mod random {
use crate::arraylist::List;
#[derive(Debug, Clone)]
pub struct Random {
x: std::num::Wrapping<u64>,
}
impl Random {
pub fn new() -> Random {
Random {
x: std::num::Wrapping(88172645463325252),
}
}
pub fn next(&mut self, n: u64) -> u64 {
self.x = self.x ^ (self.x << 7);
self.x = self.x ^ (self.x >> 9);
self.x.0 % n
}
pub fn shuffle<T>(&mut self, arr: &mut List<T>) {
let n = arr.ilen();
for i in (0..n - 1).map(|i| n - i) {
let j = self.next(i as u64) as i32;
arr.swap(i, j);
}
}
}
}
}
pub mod scanner {
use crate::arraylist::List;
use std::io::{stdin, BufReader, Bytes, Read, Stdin};
use std::str::FromStr;
macro_rules ! impl_readxn { ( $ name : ident , $ ( $ tpe : ident ) ,+ ) => { pub fn $ name <$ ( $ tpe : FromStr ) ,+> ( & mut self , n : i32 ) -> List < ( $ ( $ tpe ) ,+ ) > { ( 0 .. n ) . map ( | _ | ( $ ( self . read ::<$ tpe > ( ) ) ,+ ) ) . collect ( ) } } ; }
pub struct Scanner {
buf: Bytes<BufReader<Stdin>>,
}
impl Scanner {
pub fn new() -> Scanner {
Scanner {
buf: BufReader::new(stdin()).bytes(),
}
}
pub fn read_next<T: FromStr>(&mut self) -> Option<T> {
let token = self
.buf
.by_ref()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect::<String>();
token.parse::<T>().ok()
}
pub fn read<T: FromStr>(&mut self) -> T {
self.read_next().unwrap()
}
pub fn readn<T: FromStr>(&mut self, n: i32) -> List<T> {
(0..n).map(|_| self.read::<T>()).collect()
}
pub fn chars(&mut self) -> List<char> {
self.read::<String>().chars().collect()
}
impl_readxn!(read2n, P, Q);
impl_readxn!(read3n, P, Q, R);
impl_readxn!(read4n, P, Q, R, S);
impl_readxn!(read5n, P, Q, R, S, T);
}
}
pub mod arraylist {
use crate::{ext::range::IntRangeBounds, independent::integer::Int};
use std::fmt::Formatter;
use std::iter::FromIterator;
use std::ops::{Index, IndexMut, RangeBounds};
use std::slice::Iter;
#[derive(Clone, PartialEq, Eq)]
pub struct List<T> {
pub vec: Vec<T>,
}
impl<T> List<T> {
#[inline]
pub fn new() -> List<T> {
List { vec: vec![] }
}
#[inline]
pub fn init(init: T, n: i32) -> List<T>
where
T: Clone,
{
List {
vec: vec![init; n as usize],
}
}
#[inline]
pub fn from_vec(vec: Vec<T>) -> List<T> {
List { vec }
}
#[inline]
pub fn acc<'a, S>(n: i32, mut f: S) -> List<T>
where
S: FnMut(i32) -> T + 'a,
{
(0..n).map(|i| f(i)).collect()
}
#[inline]
pub fn ilen(&self) -> i32 {
self.vec.len() as i32
}
#[inline]
pub fn iter(&self) -> Iter<'_, T> {
self.vec.iter()
}
#[inline]
pub fn push(&mut self, item: T) {
self.vec.push(item);
}
#[inline]
pub fn sort(&mut self)
where
T: Ord,
{
self.vec.sort();
}
#[inline]
pub fn reverse(&mut self) {
self.vec.reverse();
}
#[inline]
pub fn sort_by<F>(&mut self, compare: F)
where
F: FnMut(&T, &T) -> std::cmp::Ordering,
{
self.vec.sort_by(compare)
}
#[inline]
pub fn sort_by_key<K, F>(&mut self, compare: F)
where
F: FnMut(&T) -> K,
K: Ord,
{
self.vec.sort_by_key(compare)
}
#[inline]
pub fn first(&self) -> Option<&T> {
self.vec.first()
}
#[inline]
pub fn last(&self) -> Option<&T> {
self.vec.last()
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.vec.pop()
}
#[inline]
pub fn swap(&mut self, i: i32, j: i32) {
self.vec.swap(i as usize, j as usize);
}
#[inline]
pub fn append(&mut self, mut other: Self) {
self.vec.append(&mut other.vec);
}
#[inline]
pub fn extend(&mut self, other: impl Iterator<Item = T>) {
self.vec.extend(other);
}
#[inline]
pub fn mirror(&self) -> std::iter::Cloned<Iter<T>>
where
T: Clone,
{
self.iter().cloned()
}
#[inline]
pub fn join(&self, sep: &str) -> String
where
T: std::fmt::Display,
{
self.iter()
.map(|x| format!("{}", x))
.collect::<Vec<_>>()
.join(sep)
}
#[inline]
pub fn map<B, F>(&self, f: F) -> List<B>
where
T: Clone,
F: FnMut(T) -> B,
{
self.mirror().map(f).collect()
}
#[inline]
pub fn filter<P>(&self, predicate: P) -> List<T>
where
T: Clone,
P: FnMut(&T) -> bool,
{
self.mirror().filter(predicate).collect()
}
#[inline]
pub fn filter_map<B, F>(&self, f: F) -> List<B>
where
T: Clone,
F: FnMut(T) -> Option<B>,
{
self.mirror().filter_map(f).collect()
}
#[doc = " |acc, x| -> acc"]
#[inline]
pub fn fold<B, F>(&self, init: B, f: F) -> B
where
T: Clone,
F: FnMut(B, T) -> B,
{
self.mirror().fold(init, f)
}
#[inline]
pub fn any<P>(&self, predicate: P) -> bool
where
P: FnMut(&T) -> bool,
{
self.iter().any(predicate)
}
#[inline]
pub fn all<P>(&self, predicate: P) -> bool
where
P: FnMut(&T) -> bool,
{
self.iter().all(predicate)
}
#[inline]
pub fn sum(&self) -> T
where
T: Int,
{
self.iter().cloned().fold(T::zero(), |acc, x| acc + x)
}
#[inline]
pub fn enumerate(&self) -> List<(i32, T)>
where
T: Clone,
{
self.mirror()
.enumerate()
.map(|p| (p.0 as i32, p.1))
.collect()
}
#[inline]
pub fn find<P>(&self, mut predicate: P) -> Option<&T>
where
P: FnMut(&T) -> bool,
{
self.iter().find(|x| predicate(*x))
}
#[inline]
pub fn index_of<P>(&self, mut predicate: P) -> Option<i32>
where
P: FnMut(&T) -> bool,
{
self.iter()
.enumerate()
.find(|&(_i, x)| predicate(x))
.map(|p| p.0 as i32)
}
#[inline]
pub fn to<B: FromIterator<T>>(&self) -> B
where
T: Clone,
{
self.mirror().collect()
}
#[inline]
pub fn min(&self) -> Option<&T>
where
T: Ord,
{
self.iter().min()
}
#[inline]
pub fn max(&self) -> Option<&T>
where
T: Ord,
{
self.iter().max()
}
#[inline]
pub fn argmin(&self) -> Option<i32>
where
T: Ord,
{
let item = self.iter().min()?;
self.iter()
.enumerate()
.find(|p| p.1 == item)
.map(|p| p.0 as i32)
}
#[inline]
pub fn argmax(&self) -> Option<i32>
where
T: Ord,
{
let item = self.iter().max()?;
self.iter()
.enumerate()
.find(|p| p.1 == item)
.map(|p| p.0 as i32)
}
#[inline]
pub fn part<U>(&self, range: U) -> List<T>
where
T: Clone,
U: RangeBounds<i32>,
{
List::from_vec(
self.vec[range.lower_bound(0) as usize..range.upper_bound(self.ilen()) as usize]
.to_vec(),
)
}
#[inline]
pub fn first_exn(&self) -> &T {
self.first().unwrap()
}
#[inline]
pub fn last_exn(&self) -> &T {
self.last().unwrap()
}
#[inline]
pub fn pop_exn(&mut self) -> T {
self.pop().unwrap()
}
#[inline]
pub fn min_exn(&self) -> &T
where
T: Ord,
{
self.min().unwrap()
}
#[inline]
pub fn max_exn(&self) -> &T
where
T: Ord,
{
self.max().unwrap()
}
#[inline]
pub fn argmin_exn(&self) -> i32
where
T: Ord,
{
self.argmin().unwrap()
}
#[inline]
pub fn argmax_exn(&self) -> i32
where
T: Ord,
{
self.argmax().unwrap()
}
#[inline]
pub fn find_exn<P>(&self, predicate: P) -> &T
where
P: FnMut(&T) -> bool,
{
self.find(predicate).unwrap()
}
#[inline]
pub fn index_of_exn<P>(&self, predicate: P) -> i32
where
P: FnMut(&T) -> bool,
{
self.index_of(predicate).unwrap()
}
}
impl<T> std::ops::BitXorAssign<T> for List<T> {
#[inline]
fn bitxor_assign(&mut self, rhs: T) {
self.push(rhs);
}
}
impl<T> Index<i32> for List<T> {
type Output = T;
#[inline]
fn index(&self, index: i32) -> &Self::Output {
if cfg!(debug_assertions) {
self.vec.index(index as usize)
} else {
unsafe { self.vec.get_unchecked(index as usize) }
}
}
}
impl<T> IndexMut<i32> for List<T> {
#[inline]
fn index_mut(&mut self, index: i32) -> &mut Self::Output {
if cfg!(debug_assertions) {
self.vec.index_mut(index as usize)
} else {
unsafe { self.vec.get_unchecked_mut(index as usize) }
}
}
}
impl<T> FromIterator<T> for List<T> {
fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
List {
vec: iter.into_iter().collect(),
}
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = std::vec::IntoIter<T>;
fn into_iter(self) -> std::vec::IntoIter<T> {
self.vec.into_iter()
}
}
impl<'a, T> IntoIterator for &'a List<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.vec.iter()
}
}
impl<T: std::fmt::Display> std::fmt::Display for List<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(
f,
"{}",
self.iter()
.map(|x| format!("{}", x))
.collect::<Vec<_>>()
.join(" ")
)
}
}
impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(
f,
"[{}]",
self.iter()
.map(|x| format!("{:?}", x))
.collect::<Vec<_>>()
.join(", ")
)
}
}
impl<T> From<Vec<T>> for List<T> {
fn from(vec: Vec<T>) -> Self {
Self::from_vec(vec)
}
}
impl<T: Clone> From<&[T]> for List<T> {
fn from(slice: &[T]) -> Self {
slice.iter().cloned().collect()
}
}
#[macro_export]
macro_rules ! list { ( ) => { $ crate :: arraylist :: List :: new ( ) } ; ( $ ( $ v : expr ) ,+ $ ( , ) ? ) => { $ crate :: arraylist :: List :: from_vec ( [ $ ( $ v ) ,+ ] . to_vec ( ) ) } ; ( $ v : expr ; $ a : expr ) => { $ crate :: arraylist :: List :: init ( $ v , $ a ) } ; ( $ v : expr ; $ a : expr ; $ ( $ rest : expr ) ;+ ) => { $ crate :: arraylist :: List :: init ( list ! ( $ v ; $ ( $ rest ) ;+ ) , $ a ) } ; }
}
pub mod data_structure {
pub mod treap {
use crate::independent::random::Random;
use std::cmp::Ordering;
use std::iter::FromIterator;
use std::ops::Range;
#[derive(Debug, Clone)]
struct Node<T, U> {
key: T,
value: U,
priority: u64,
l: Link<T, U>,
r: Link<T, U>,
}
impl<T, U> Node<T, U> {
fn new(key: T, value: U, priority: u64) -> Self {
Node {
key,
value,
priority,
l: None,
r: None,
}
}
}
type NonNull<T, U> = Box<Node<T, U>>;
type Link<T, U> = Option<NonNull<T, U>>;
fn split<T: Ord, U>(now: Link<T, U>, key: &T) -> (Link<T, U>, Link<T, U>) {
match now {
None => (None, None),
Some(node) => {
let mut node = node;
if key <= &node.key {
let (nl, nr) = split(node.l.take(), key);
node.l = nr;
(nl, Some(node))
} else {
let (nl, nr) = split(node.r.take(), key);
node.r = nl;
(Some(node), nr)
}
}
}
}
fn merge<T, U>(l_tree: &mut Link<T, U>, r_tree: Link<T, U>) {
match (l_tree.take(), r_tree) {
(Some(mut l_node), Some(mut r_node)) => {
if l_node.priority > r_node.priority {
merge(&mut l_node.r, Some(r_node));
*l_tree = Some(l_node);
} else {
let mut new_tree = Some(l_node);
merge(&mut new_tree, r_node.l.take());
r_node.l = new_tree;
*l_tree = Some(r_node);
}
}
(new_tree, None) | (None, new_tree) => *l_tree = new_tree,
}
}
fn insert<T: Ord, U>(tree: &mut Link<T, U>, new_node: Node<T, U>) {
let (mut left, right) = split(tree.take(), &new_node.key);
merge(&mut left, Some(Box::new(new_node)));
merge(&mut left, right);
*tree = left.take();
}
fn remove<T: Ord, U>(tree: &mut Link<T, U>, key: &T) {
let mut new_tree;
match tree {
Some(ref mut node) => match key.cmp(&node.key) {
Ordering::Less => {
remove(&mut node.l, key);
return;
}
Ordering::Greater => {
remove(&mut node.r, key);
return;
}
Ordering::Equal => {
new_tree = node.l.take();
merge(&mut new_tree, node.r.take());
}
},
None => return,
}
std::mem::replace(tree, new_tree);
}
fn get<'a, T: Ord, U>(tree: &'a Link<T, U>, key: &T) -> Option<(&'a T, &'a U)> {
tree.as_ref().and_then(|node| match key.cmp(&node.key) {
Ordering::Less => get(&node.l, key),
Ordering::Greater => get(&node.r, key),
Ordering::Equal => Some((&node.key, &node.value)),
})
}
fn next<'a, T: Ord, U>(
tree: &'a Link<T, U>,
key: &T,
inclusive: bool,
) -> Option<(&'a T, &'a U)> {
tree.as_ref().and_then(|node| match key.cmp(&node.key) {
Ordering::Greater => next(&node.r, key, inclusive),
Ordering::Less => match next(&node.l, key, inclusive) {
None => Some((&node.key, &node.value)),
res => res,
},
Ordering::Equal => {
if inclusive {
Some((&node.key, &node.value))
} else {
next(&node.r, key, inclusive)
}
}
})
}
fn prev<'a, T: Ord, U>(
tree: &'a Link<T, U>,
key: &T,
inclusive: bool,
) -> Option<(&'a T, &'a U)> {
tree.as_ref().and_then(|node| match key.cmp(&node.key) {
Ordering::Less => prev(&node.l, key, inclusive),
Ordering::Greater => match prev(&node.r, key, inclusive) {
None => Some((&node.key, &node.value)),
res => res,
},
Ordering::Equal => {
if inclusive {
Some((&node.key, &node.value))
} else {
prev(&node.l, key, inclusive)
}
}
})
}
fn min<T: Ord, U>(tree: &Link<T, U>) -> Option<(&T, &U)> {
tree.as_ref().and_then(|node| {
let mut curr = node;
while let Some(ref left_node) = curr.l {
curr = left_node;
}
Some((&curr.key, &curr.value))
})
}
fn max<T: Ord, U>(tree: &Link<T, U>) -> Option<(&T, &U)> {
tree.as_ref().and_then(|node| {
let mut curr = node;
while let Some(ref right_node) = curr.r {
curr = right_node;
}
Some((&curr.key, &curr.value))
})
}
fn keyof<'a, T, U>(tpl: Option<(&'a T, &U)>) -> Option<&'a T> {
tpl.map(|t| t.0)
}
fn identity<T>(arg: T) -> T {
arg
}
#[derive(Debug, Clone)]
pub struct TreapMap<T, U> {
tree: Link<T, U>,
rng: Random,
}
#[derive(Debug, Clone)]
pub struct TreapSet<T> {
tree: Link<T, ()>,
rng: Random,
}
macro_rules ! treap_impl { ( $ rt : ty , $ mapfn : ident ) => { pub fn new ( ) -> Self { Self { tree : None , rng : Random :: new ( ) } } pub fn remove ( & mut self , key : & T ) { let tree = & mut self . tree ; remove ( tree , key ) ; } pub fn erase ( & mut self , range : Range < T > ) { let right = self . split_off ( & range . end ) ; self . split_off ( & range . start ) ; self . merge ( right ) ; } pub fn contains ( & self , key : & T ) -> bool { let tree = & self . tree ; get ( tree , key ) . is_some ( ) } pub fn prev ( & self , key : & T , inclusive : bool ) -> Option <$ rt > { let tree = & self . tree ; $ mapfn ( prev ( tree , key , inclusive ) ) } pub fn next ( & self , key : & T , inclusive : bool ) -> Option <$ rt > { let tree = & self . tree ; $ mapfn ( next ( tree , key , inclusive ) ) } pub fn min ( & self ) -> Option <$ rt > { let tree = & self . tree ; $ mapfn ( min ( tree ) ) } pub fn max ( & self ) -> Option <$ rt > { let tree = & self . tree ; $ mapfn ( max ( tree ) ) } pub fn min_exn ( & self ) -> $ rt { self . min ( ) . unwrap ( ) } pub fn max_exn ( & self ) -> $ rt { self . max ( ) . unwrap ( ) } # [ doc = " self = (∞, key) & return = [key, ∞)" ] pub fn split_off ( & mut self , key : & T ) -> Self { let tree = & mut self . tree ; let ( mut left , right ) = split ( tree . take ( ) , key ) ; * tree = left . take ( ) ; Self { tree : right , rng : Random :: new ( ) } } pub fn merge ( & mut self , right : Self ) { let tree = & mut self . tree ; merge ( tree , right . tree ) } pub fn ilen ( & self ) -> i32 { self . iter ( ) . count ( ) as i32 } pub fn is_empty ( & self ) -> bool { self . min ( ) . is_none ( ) } pub fn get ( & self , key : & T ) -> Option <$ rt > { let tree = & self . tree ; $ mapfn ( get ( tree , key ) ) } } ; }
impl<T: Ord> TreapSet<T> {
treap_impl! { & T , keyof }
}
impl<T: Ord, U> TreapMap<T, U> {
treap_impl! { ( & T , & U ) , identity }
}
impl<T: Ord> TreapSet<T> {
pub fn insert(&mut self, key: T) {
let tree = &mut self.tree;
let new_node = Node::new(key, (), self.rng.next(std::u64::MAX));
insert(tree, new_node);
}
pub fn iter(&self) -> impl Iterator<Item = &T> {
(0..).scan(
(&self.tree, Vec::<&Node<T, ()>>::new()),
|(current, stack), _| {
while let Some(ref node) = current {
*current = &node.l;
stack.push(node);
}
stack.pop().map(|node| {
let Node { ref key, ref r, .. } = node;
*current = r;
key
})
},
)
}
pub fn range(&self, range: Range<T>) -> impl Iterator<Item = &T> {
(0..).scan(self.next(&range.start, true), move |state, _| {
if let &mut Some(t) = state {
if t >= &range.end {
return None;
}
*state = self.next(t, false);
Some(t)
} else {
return None;
}
})
}
}
impl<T: Ord, U> TreapMap<T, U> {
pub fn insert(&mut self, key: T, value: U) {
let tree = &mut self.tree;
let new_node = Node::new(key, value, self.rng.next(std::u64::MAX));
insert(tree, new_node);
}
pub fn iter(&self) -> impl Iterator<Item = (&T, &U)> {
(0..).scan(
(&self.tree, Vec::<&Node<T, U>>::new()),
|(current, stack), _| {
while let Some(ref node) = current {
*current = &node.l;
stack.push(node);
}
stack.pop().map(|node| {
let Node {
ref key,
ref value,
ref r,
..
} = node;
*current = r;
(key, value)
})
},
)
}
pub fn range(&self, range: Range<T>) -> impl Iterator<Item = (&T, &U)> {
(0..).scan(self.next(&range.start, true), move |state, _| {
if let &mut Some(t) = state {
if t.0 >= &range.end {
return None;
}
*state = self.next(t.0, false);
Some(t)
} else {
return None;
}
})
}
}
impl<T: Ord> FromIterator<T> for TreapSet<T> {
fn from_iter<V: IntoIterator<Item = T>>(iter: V) -> Self {
let mut set = TreapSet::new();
for i in iter {
set.insert(i);
}
set
}
}
impl<T: Ord, U> FromIterator<(T, U)> for TreapMap<T, U> {
fn from_iter<V: IntoIterator<Item = (T, U)>>(iter: V) -> Self {
let mut set = TreapMap::new();
for (i, j) in iter {
set.insert(i, j);
}
set
}
}
}
}
pub mod ext {
pub mod range {
use crate::independent::integer::Int;
use std::cmp::{max, min};
use std::ops::{Bound, Range, RangeBounds};
pub trait IntRangeBounds<U: Int>: RangeBounds<U> {
fn lbopt(&self) -> Option<U> {
match self.start_bound() {
Bound::Included(x) => Some(*x),
Bound::Excluded(x) => Some(*x + U::one()),
Bound::Unbounded => None,
}
}
fn ubopt(&self) -> Option<U> {
match self.end_bound() {
Bound::Included(x) => Some(*x + U::one()),
Bound::Excluded(x) => Some(*x),
Bound::Unbounded => None,
}
}
#[doc = " inclusive"]
fn lower_bound(&self, limit: U) -> U {
self.lbopt().map_or(limit, |x| max(limit, x))
}
#[doc = " exclusive"]
fn upper_bound(&self, limit: U) -> U {
self.ubopt().map_or(limit, |x| min(limit, x))
}
fn to_harfopen(&self, lb: U, ub: U) -> Range<U> {
self.lower_bound(lb)..self.upper_bound(ub)
}
fn width(&self) -> U {
if self.empty() {
U::zero()
} else {
self.ubopt().unwrap() - self.lbopt().unwrap()
}
}
fn empty(&self) -> bool {
self.lbopt().is_none()
|| self.ubopt().is_none()
|| !(self.lbopt().unwrap() < self.ubopt().unwrap())
}
fn contain_range(&self, inner: &Self) -> bool {
(match (self.lbopt(), inner.lbopt()) {
(Some(a), Some(b)) => a <= b,
(None, _) => true,
(Some(_), None) => false,
}) && (match (inner.ubopt(), self.ubopt()) {
(Some(a), Some(b)) => a <= b,
(_, None) => true,
(None, Some(_)) => false,
})
}
fn separate_range(&self, other: &Self) -> bool {
if let (Some(a), Some(b)) = (self.ubopt(), other.lbopt()) {
a <= b
} else if let (Some(a), Some(b)) = (other.ubopt(), self.lbopt()) {
a <= b
} else {
false
}
}
fn overlap(&self, other: &Self) -> Range<U> {
let left = if let (Some(a), Some(b)) = (self.lbopt(), other.lbopt()) {
max(a, b)
} else {
self.lbopt().or(other.lbopt()).unwrap()
};
let right = if let (Some(a), Some(b)) = (self.ubopt(), other.ubopt()) {
min(a, b)
} else {
self.ubopt().or(other.ubopt()).unwrap()
};
left..right
}
}
impl<T: ?Sized, U: Int> IntRangeBounds<U> for T where T: RangeBounds<U> {}
}
}