結果
| 問題 | No.2421 entersys? |
| ユーザー |
👑  zeronosu77108
|
| 提出日時 | 2023-08-12 14:29:19 |
| 言語 | Rust (1.77.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 33,045 bytes |
| コンパイル時間 | 11,983 ms |
| コンパイル使用メモリ | 401,092 KB |
| 実行使用メモリ | 90,340 KB |
| 最終ジャッジ日時 | 2024-04-30 06:15:13 |
| 合計ジャッジ時間 | 21,865 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | AC | 627 ms
66,608 KB |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | AC | 457 ms
72,780 KB |
| testcase_27 | AC | 456 ms
73,068 KB |
| testcase_28 | AC | 454 ms
72,164 KB |
コンパイルメッセージ
warning: unnecessary parentheses around block return value
--> src/main.rs:825:9
|
825 | (base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize)
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
825 - (base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize)
825 + base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize
|
warning: unused variable: `i`
--> src/main.rs:52:14
|
52 | |&(a,i):&(Self::Type,usize), &b:&Self::F| a + b
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:186:13
|
186 | let mut left = match range.start_bound() {
| ----^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:191:13
|
191 | let mut right = match range.end_bound() {
| ----^^^^^
| |
| help: remove this `mut`
ソースコード
fn main() {
let mut sc = Scanner::new();
let n = sc.usize();
let mut times = vec![];
let mut xlr = vec![];
for _ in 0..n {
let x = sc.input::<String>();
let l = sc.usize();
let r = sc.usize();
xlr.push((x, l, r));
times.push(l);
times.push(r);
}
let q = sc.usize();
let mut queries : Vec<(u8, String, usize, usize)> = vec![];
for _ in 0..q {
let t = sc.u8();
match t {
1 => {
let x = sc.input::<String>();
let time = sc.usize();
queries.push((t, x, time, 0));
times.push(time);
}
2 => {
let time = sc.usize();
queries.push((t, "".to_string(), time, 0));
times.push(time);
}
3 => {
let x = sc.input::<String>();
let l = sc.usize();
let r = sc.usize();
queries.push((t, x, l, r));
times.push(l);
times.push(r);
}
_ => unreachable!()
}
}
times.sort(); times.dedup();
def_map_monoid!(M,
i64,
i64,
0,
|&a:&Self::Type, &b:&Self::Type| a.max(b),
|&a:&Self::F,&b:&Self::F| a + b,
|&(a,i):&(Self::Type,usize), &b:&Self::F| a + b
);
let mut id = BTreeMap::new();
let mut now = 0;
let mut sets = vec![];
let mut seg = LazySegmentTree::<M>::new(times.len());
for (x, l, r) in xlr {
let l = times.binary_search(&l).unwrap();
let r = times.binary_search(&r).unwrap();
seg.update(l..=r, 1);
if !id.contains_key(&x) {
id.insert(x.clone(), now);
now += 1;
sets.push(RangeSet::new(true));
}
let id = id[&x];
sets[id].insert_range(l as i64 ..=r as i64);
}
for i in 0..q {
match queries[i] {
(1, ref x, time, _) => {
let time = times.binary_search(&time).unwrap();
let id = id[x];
if sets[id].contains(time as i64) {
println!("Yes");
} else {
println!("No");
}
}
(2, _, time, _) => {
let time = times.binary_search(&time).unwrap();
let ans = seg.fold(time..=time);
println!("{}", ans);
}
(3, ref x, l, r) => {
let l = times.binary_search(&l).unwrap();
let r = times.binary_search(&r).unwrap();
if !id.contains_key(x) {
id.insert(x.clone(), now);
now += 1;
sets.push(RangeSet::new(true));
}
let id = id[x];
seg.update(l..=r, 1);
sets[id].insert_range(l as i64..r as i64);
}
_ => unreachable!()
}
}
}
struct RangeSet {
ranges: std::collections::BTreeSet<(i64, i64)>,
len: i64,
merge_adjacent_range_flag: bool
}
#[allow(dead_code)]
impl RangeSet {
fn new(merge_adjacent_range_flag: bool) -> Self {
Self { ranges: std::collections::BTreeSet::new(), len:0, merge_adjacent_range_flag }
}
fn contains(&self, x:i64) -> bool {
self.contains_range(x..=x)
}
fn contains_range<R:std::ops::RangeBounds<i64>>(&self, range:R) -> bool {
let left = match range.start_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&l) => l,
_ => unreachable!()
};
let right = match range.end_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
};
if let Some(&(l2, r2)) = self.ranges.range((left,left)..).next() {
if l2 <= left && right <= r2 { return true; }
}
if let Some(&(l2, r2)) = self.ranges.range(..(left,left)).next_back() {
if l2 <= left && right <= r2 { return true; }
}
false
}
fn insert(&mut self, x:i64) -> (i64, i64) {
self.insert_range(x..=x)
}
fn insert_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> (i64, i64) {
let mut left = match range.start_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&l) => l,
_ => unreachable!()
};
let mut right = match range.end_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
};
let mut erase = vec![];
for &(l, r) in self.ranges.range((left,left)..=(right,right)) {
left = left.min(l);
right = right.max(r);
erase.push((l, r));
}
if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {
if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} { left = left.min(prev.0); right = right.max(prev.1); erase.push(prev); }
}
if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {
if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} { left = left.min(next.0); right = right.max(next.1); erase.push(next); }
}
for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }
self.ranges.insert((left, right));
self.len += right - left;
(left, right)
}
fn remove(&mut self, x:i64) -> () {
self.remove_range(x..=x);
}
fn remove_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> () {
let mut left = match range.start_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&l) => l,
_ => unreachable!()
};
let mut right = match range.end_bound() {
std::ops::Bound::Unbounded => unreachable!(),
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
};
let mut erase = vec![];
let mut add = vec![];
for &(l, r) in self.ranges.range((left,left)..=(right,right)) {
if right < r { add.push((right, r)); }
if l < left { add.push((l, left)); }
erase.push((l, r));
}
if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {
if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} {
if prev.0 < left { add.push((prev.0, left)); }
if right < prev.1 { add.push((right, prev.1)); }
erase.push(prev);
}
}
if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {
if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} {
if next.0 < left { add.push((next.0, left)); }
if right < next.1 { add.push((right, next.1)); }
erase.push(next);
}
}
for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }
for a in add { self.ranges.insert(a); self.len += a.1 - a.0 }
}
fn ranges_count(&self) -> usize {
self.ranges.len()
}
fn len(&self) -> i64 {
self.len
}
fn iter(&self) -> std::collections::btree_set::Iter<'_, (i64, i64)> {
self.ranges.iter()
}
fn mex(&self, mut x:i64) -> i64 {
if let Some(prev) = self.ranges.range(..=(x,std::i64::MAX)).next_back() {
if x <= prev.0 { x = prev.1 + 1; }
}
x
}
}
#[macro_export]
macro_rules! def_map_monoid {
($m:ident, $t1:ty, $t2:ty, $id:expr, $op:expr, $merge:expr, $eval:expr) => {
pub struct $m;
impl MapMonoid for $m {
type Type = $t1;
type F = $t2;
fn identity() -> Self::Type { $id }
fn operator(x:&Self::Type, y:&Self::Type) -> Self::Type { $op(x, y) }
fn merge(x:&Option<Self::F>, y:&Option<Self::F>) -> Option<Self::F> {
match (x, y) {
(None, None) => None,
(Some(x), Some(y)) => Some($merge(x, y)),
(&x, None) => x,
(None, &y) => y
}
}
fn eval(x:&(Self::Type, usize), y:&Self::F) -> Self::Type {
$eval(x, y)
}
}
};
}
pub trait MapMonoid {
type Type: Copy + Clone + std::fmt::Debug;
type F: Copy + Clone + std::fmt::Debug;
fn identity() -> Self::Type;
fn operator(a: &Self::Type, b: &Self::Type) -> Self::Type;
fn merge(a: &Option<Self::F>, b: &Option<Self::F>) -> Option<Self::F>;
fn eval(a: &(Self::Type, usize), b: &Self::F) -> Self::Type;
}
struct LazySegmentTree<T: MapMonoid> {
n: usize,
seg: Vec<(T::Type, usize)>,
lazy: Vec<Option<T::F>>,
}
#[allow(unused)]
impl<T: MapMonoid> LazySegmentTree<T> {
pub fn new(n: usize) -> Self {
let mut seg = vec![(T::identity(), 1); 2*n+1];
for i in (1..n).rev() { seg[i].1 = seg[2*i].1 + seg[2*i+1].1; }
Self { n, seg: seg, lazy: vec![None; 2 * n + 1] }
}
pub fn from(s: &[T::Type]) -> Self {
let n = s.len();
let mut seg = vec![(T::identity(), 1); 2 * n + 1];
for (i, &si) in s.iter().enumerate() { seg[i + n].0 = si; }
for i in (1..n).rev() {
seg[i].0 = T::operator(&seg[2 * i].0, &seg[2 * i + 1].0);
seg[i].1 = &seg[2 * i].1 + &seg[2 * i + 1].1;
}
LazySegmentTree { n, seg, lazy: vec![None; 2 * n + 1] }
}
fn eval(&mut self, i: usize) -> T::Type {
if let Some(x) = self.lazy[i] {
T::eval(&self.seg[i], &x)
} else {
self.seg[i].0
}
}
fn propagate_at(&mut self, i: usize) {
self.seg[i] = (self.eval(i), self.seg[i].1);
self.lazy[i*2] = T::merge(&self.lazy[i * 2], &self.lazy[i]);
self.lazy[i*2 + 1] = T::merge(&self.lazy[i * 2 + 1], &self.lazy[i]);
self.lazy[i] = None;
}
fn propagate_above(&mut self, i: usize) {
let height = 63u32.saturating_sub(i.leading_zeros());
for h in (1..=height).rev() {
self.propagate_at(i >> h);
}
}
fn recalc_above(&mut self, mut i: usize) {
while i > 0 {
i /= 2;
let left = self.eval(i * 2);
let right = self.eval(i * 2 + 1);
self.seg[i].0 = T::operator(&left, &right);
}
}
fn _update(&mut self, mut l: usize, mut r: usize, x: T::F) {
let l0 = l / (l & l.wrapping_neg());
let r0 = r / (r & r.wrapping_neg()) - 1;
self.propagate_above(l0);
self.propagate_above(r0);
while l < r {
if l % 2 == 1 {
self.lazy[l] = T::merge(&self.lazy[l], &Some(x));
l += 1;
}
if r % 2 == 1 {
r -= 1;
self.lazy[r] = T::merge(&self.lazy[r], &Some(x));
}
l /= 2;
r /= 2;
}
self.recalc_above(l0);
self.recalc_above(r0);
}
pub fn update<R: std::ops::RangeBounds<usize>>(&mut self, range: R, x: T::F) {
let l = self.n + match range.start_bound() {
std::ops::Bound::Unbounded => 0,
std::ops::Bound::Included(&l) => l,
_ => unreachable!()
};
let r = self.n + match range.end_bound() {
std::ops::Bound::Unbounded => self.n,
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
};
self._update(l, r, x)
}
fn _fold(&mut self, mut l: usize, mut r: usize) -> T::Type {
let mut left = T::identity();
let mut right = T::identity();
self.propagate_above(l / (l & l.wrapping_neg()));
self.propagate_above(r / (r & r.wrapping_neg()) - 1);
while l < r {
if l % 2 == 1 {
left = T::operator(&left, &self.eval(l));
l += 1;
}
if r % 2 == 1 {
r -= 1;
right = T::operator(&self.eval(r), &right);
}
l /= 2;
r /= 2;
}
T::operator(&left, &right)
}
pub fn fold<R: std::ops::RangeBounds<usize>>(&mut self, range: R) -> T::Type {
let l = self.n + match range.start_bound() {
std::ops::Bound::Unbounded => 0,
std::ops::Bound::Included(&l) => l,
_ => unreachable!()
};
let r = self.n + match range.end_bound() {
std::ops::Bound::Unbounded => self.n,
std::ops::Bound::Included(&x) => x + 1,
std::ops::Bound::Excluded(&x) => x,
};
self._fold(l, r)
}
pub fn get(&mut self, index: usize) -> T::Type { self.fold(index..=index) }
}
struct Scanner { s : std::collections::VecDeque<String> } #[allow(unused)] impl Scanner { fn new() -> Self { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); Self { s : s.split_whitespace().map(|s| s.to_string()).collect() } } fn reload(&mut self) -> () { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); self.s = s.split_whitespace().map(|s| s.to_string()).collect(); } fn usize(&mut self) -> usize { self.input() } fn usize1(&mut self) -> usize { self.input::<usize>() - 1 } fn isize(&mut self) -> isize { self.input() } fn i32(&mut self) -> i32 { self.input() } fn i64(&mut self) -> i64 { self.input() } fn i128(&mut self) -> i128 { self.input() } fn u8(&mut self) -> u8 { self.input() } fn u32(&mut self) -> u32 { self.input() } fn u64(&mut self) -> u64 { self.input() } fn u128(&mut self) -> u128 { self.input() } fn edge(&mut self) -> (usize, usize) { (self.usize1(), self.usize1()) } fn edges(&mut self, m : usize) -> Vec<(usize, usize)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.edge()); } e } fn wedge<T:std::str::FromStr>(&mut self) -> (usize, usize, T) { (self.usize1(), self.usize1(), self.input()) } fn wedges<T:std::str::FromStr>(&mut self, m : usize) -> Vec<(usize, usize, T)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.wedge()); } e } fn input<T>(&mut self) -> T where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } if let Some(head) = self.s.pop_front() { head.parse::<T>().ok().unwrap() } else { panic!() } } fn tuple<T, U>(&mut self) -> (T, U) where T: std::str::FromStr, U: std::str::FromStr { (self.input(), self.input()) } fn vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } self.s.drain(..n).map(|s| s.parse::<T>().ok().unwrap() ).collect::<Vec<T>>() } fn nvec<T>(&mut self) -> Vec<T> where T: std::str::FromStr { let n : usize = self.input(); self.vec(n) } fn chars(&mut self) -> Vec<char> { let s : String = self.input(); s.chars().collect() } fn bytes(&mut self) -> Vec<u8> { let s : String = self.input(); s.bytes().collect() } }
// Copyright 2017 Alkis Evlogimenos
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
use std::cmp::Ordering::{self, Less, Greater};
use std::collections::BTreeMap;
/// Extends [`slice`] with fast operations on ordered slices.
///
/// [`slice`]: https://doc.rust-lang.org/stable/std/primitive.slice.html
pub trait Ext {
type Item;
/// Returns the index `i` pointing to the first element in the ordered slice
/// that is _not less_ than `x`.
///
/// The slice MUST be ordered by the order defined by its elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.lower_bound(&9), 0);
/// assert_eq!(a.lower_bound(&10), 0);
/// assert_eq!(a.lower_bound(&11), 1);
/// assert_eq!(a.lower_bound(&12), 2);
/// assert_eq!(a.lower_bound(&13), 2);
/// assert_eq!(a.lower_bound(&14), 4);
/// assert_eq!(a.lower_bound(&15), 4);
/// assert_eq!(a.lower_bound(&16), 5);
/// ```
fn lower_bound(&self, x: &Self::Item) -> usize
where
Self::Item: Ord;
/// Returns the index `i` pointing to the first element in the ordered slice
/// for which `f(self[i]) != Less`.
///
/// The slice MUST be ordered by the order defined by the comparator
/// function. The comparator function should take an element and return
/// `Ordering` that is consistent with the ordering of the slice.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [1, 2, 3, 6, 9, 9];
/// assert_eq!(b.lower_bound(&3), b.lower_bound_by(|x| x.cmp(&3)));
/// ```
fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
where
F: FnMut(&'a Self::Item) -> Ordering;
/// Returns the index `i` pointing to the first element in the ordered slice
/// for which `f(self[i]) >= k`.
///
/// The slice MUST be ordered by the order defined by the keys of its
/// elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [1, 2, 3, 6, 9, 9];
/// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));
/// ```
fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
where
F: FnMut(&'a Self::Item) -> K,
K: Ord;
/// Returns the index `i` pointing to the first element in the ordered slice
/// that is _greater_ than `x`.
///
/// The slice MUST be ordered by the order defined by its elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.upper_bound(&9), 0);
/// assert_eq!(a.upper_bound(&10), 1);
/// assert_eq!(a.upper_bound(&11), 2);
/// assert_eq!(a.upper_bound(&12), 2);
/// assert_eq!(a.upper_bound(&13), 4);
/// assert_eq!(a.upper_bound(&14), 4);
/// assert_eq!(a.upper_bound(&15), 5);
/// assert_eq!(a.upper_bound(&16), 5);
/// ```
fn upper_bound(&self, x: &Self::Item) -> usize
where
Self::Item: Ord;
/// Returns the index `i` pointing to the first element in the ordered slice
/// for which `f(self[i]) == Greater`.
///
/// The slice MUST be ordered by the order defined by the comparator
/// function. The comparator function should take an element and return
/// `Ordering` that is consistent with the ordering of the slice.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [1, 2, 3, 6, 9, 9];
/// assert_eq!(b.upper_bound(&3), b.upper_bound_by(|x| x.cmp(&3)));
/// ```
fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
where
F: FnMut(&'a Self::Item) -> Ordering;
/// Returns the index `i` pointing to the first element in the ordered slice
/// for which `f(self[i]) > k`.
///
/// The slice MUST be ordered by the order defined by the keys of its
/// elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [1, 2, 3, 6, 9, 9];
/// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));
fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
where
F: FnMut(&'a Self::Item) -> K,
K: Ord;
/// Returns the [`Range`] `a..b` such that all elements in `self[a..b]` are
/// _equal_ to `x`.
///
/// The slice MUST be ordered by the order defined by its elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [10, 11, 13, 13, 15];
/// for i in 9..17 {
/// assert_eq!(b.equal_range(&i), (b.lower_bound(&i)..b.upper_bound(&i)));
/// }
/// ```
/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
fn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>
where
Self::Item: Ord;
/// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`
/// `f(e) == Equal`.
///
/// The slice MUST be ordered by the order defined by the comparator
/// function. The comparator function should take an element and return
/// `Ordering` that is consistent with the ordering of the slice.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [10, 11, 13, 13, 15];
/// for i in 9..17 {
/// assert_eq!(b.equal_range(&i), b.equal_range_by(|x| x.cmp(&i)));
/// }
/// ```
/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
fn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize>
where
F: FnMut(&'a Self::Item) -> Ordering;
/// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`
/// `f(e) == k`.
///
/// The slice MUST be ordered by the order defined by the keys of its
/// elements.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let b = [10, 11, 13, 13, 15];
/// for i in 9..17 {
/// let i2 = i * 2;
/// assert_eq!(b.equal_range(&i), b.equal_range_by_key(&i2, |x| x * 2));
/// }
/// ```
/// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
fn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> std::ops::Range<usize>
where
F: FnMut(&'a Self::Item) -> K,
K: Ord;
/// Transforms the slice into the next permutation from the set of all
/// permutations that are lexicographically ordered with respect to the
/// natural order of T. Returns true if such permutation exists, otherwise
/// transforms the range into the first permutation and returns false.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let mut b = [2, 1, 3];
/// let mut v = Vec::new();
/// for _ in 0..6 {
/// let x = b.next_permutation();
/// v.push((x, b.to_vec()));
/// }
/// assert_eq!(v, &[(true, [2, 3, 1].to_vec()),
/// (true, [3, 1, 2].to_vec()),
/// (true, [3, 2, 1].to_vec()),
/// (false, [1, 2, 3].to_vec()),
/// (true, [1, 3, 2].to_vec()),
/// (true, [2, 1, 3].to_vec())]);
fn next_permutation(&mut self) -> bool
where
Self::Item: Ord;
/// Transforms the slice into the previous permutation from the set of all
/// permutations that are lexicographically ordered with respect to the
/// natural order of T. Returns true if such permutation exists, otherwise
/// transforms the range into the last permutation and returns false.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let mut b = [2, 1, 3];
/// let mut v = Vec::new();
/// for _ in 0..6 {
/// let x = b.prev_permutation();
/// v.push((x, b.to_vec()));
/// }
/// assert_eq!(v, &[(true, [1, 3, 2].to_vec()),
/// (true, [1, 2, 3].to_vec()),
/// (false, [3, 2, 1].to_vec()),
/// (true, [3, 1, 2].to_vec()),
/// (true, [2, 3, 1].to_vec()),
/// (true, [2, 1, 3].to_vec())]);
fn prev_permutation(&mut self) -> bool
where
Self::Item: Ord;
/// Applies `permutation` to the slice. For each element at index `i` the
/// following holds:
///
/// new_self[i] == old_self[permutation[i]]
///
/// The transformation happens in O(N) time and O(1) space. `permutation`
/// is mutated during the transformation but it is restored to its original
/// state on return.
///
/// # Panics
///
/// This function panics if `self` and `permutation` do not have the same
/// length or any value in `permutation` is not in `0..self.len()`.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let mut b = ['d', 'a', 'c', 'b'];
/// let mut p = [1, 3, 2, 0];
/// b.apply_permutation(&mut p);
/// assert_eq!(b, ['a', 'b', 'c', 'd']);
/// assert_eq!(p, [1, 3, 2, 0]);
fn apply_permutation(&mut self, permutation: &mut [isize]);
/// Applies the inverse of `permutation` to the slice. For each element at
/// index `i` the following holds:
///
/// new_self[permutation[i]] == old_self[i]
///
/// The transformation happens in O(N) time and O(1) space. `permutation`
/// is mutated during the transformation but it is restored to its original
/// state on return.
///
/// # Panics
///
/// This function panics if `self` and `permutation` do not have the same
/// length or any value in `permutation` is not in `0..self.len()`.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let mut b = ['d', 'a', 'c', 'b'];
/// let mut p = [3, 0, 2, 1];
/// b.apply_inverse_permutation(&mut p);
/// assert_eq!(b, ['a', 'b', 'c', 'd']);
/// assert_eq!(p, [3, 0, 2, 1]);
fn apply_inverse_permutation(&mut self, permutation: &mut [isize]);
}
impl<T> Ext for [T] {
type Item = T;
fn lower_bound(&self, x: &Self::Item) -> usize
where
T: Ord,
{
self.lower_bound_by(|y| y.cmp(x))
}
fn lower_bound_by<'a, F>(&'a self, mut f: F) -> usize
where
F: FnMut(&'a Self::Item) -> Ordering,
{
let s = self;
let mut size = s.len();
if size == 0 {
return 0;
}
let mut base = 0usize;
while size > 1 {
let half = size / 2;
let mid = base + half;
let cmp = f(unsafe { s.get_unchecked(mid) });
base = if cmp == Less { mid } else { base };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
base + (cmp == Less) as usize
}
fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usize
where
F: FnMut(&'a Self::Item) -> K,
K: Ord,
{
self.lower_bound_by(|e| f(e).cmp(k))
}
fn upper_bound(&self, x: &Self::Item) -> usize
where
T: Ord,
{
self.upper_bound_by(|y| y.cmp(x))
}
fn upper_bound_by<'a, F>(&'a self, mut f: F) -> usize
where
F: FnMut(&'a Self::Item) -> Ordering,
{
let s = self;
let mut size = s.len();
if size == 0 {
return 0;
}
let mut base = 0usize;
while size > 1 {
let half = size / 2;
let mid = base + half;
let cmp = f(unsafe { s.get_unchecked(mid) });
base = if cmp == Greater { base } else { mid };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
base + (cmp != Greater) as usize
}
fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usize
where
F: FnMut(&'a Self::Item) -> K,
K: Ord,
{
self.upper_bound_by(|e| f(e).cmp(k))
}
fn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>
where
T: Ord,
{
self.equal_range_by(|y| y.cmp(x))
}
fn equal_range_by<'a, F>(&'a self, mut f: F) -> std::ops::Range<usize>
where
F: FnMut(&'a Self::Item) -> Ordering,
{
let s = self;
let mut size = s.len();
if size == 0 {
return 0..0;
}
let mut base = (0usize, 0usize);
while size > 1 {
let half = size / 2;
let mid = (base.0 + half, base.1 + half);
let cmp = (
f(unsafe { s.get_unchecked(mid.0) }),
f(unsafe { s.get_unchecked(mid.1) }),
);
base = (
if cmp.0 == Less { mid.0 } else { base.0 },
if cmp.1 == Greater { base.1 } else { mid.1 },
);
size -= half;
}
let cmp = (
f(unsafe { s.get_unchecked(base.0) }),
f(unsafe { s.get_unchecked(base.1) }),
);
(base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize)
}
fn equal_range_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> std::ops::Range<usize>
where
F: FnMut(&'a Self::Item) -> K,
K: Ord,
{
self.equal_range_by(|e| f(e).cmp(k))
}
fn next_permutation(&mut self) -> bool
where
Self::Item: Ord
{
// Adapted from http://en.cppreference.com/w/cpp/algorithm/next_permutation.
if self.len() <= 1 { return false; }
let last = self.len() - 1;
let mut a = last;
loop {
let mut b = a;
a -= 1;
if self[a] < self[b] {
b = last;
while self[a] >= self[b] {
b -= 1;
}
self.swap(a, b);
self[a+1..].reverse();
return true;
}
if a == 0 {
self.reverse();
return false;
}
}
}
fn prev_permutation(&mut self) -> bool
where
Self::Item: Ord
{
// Adapted from http://en.cppreference.com/w/cpp/algorithm/prev_permutation.
if self.len() <= 1 { return false; }
let last = self.len() - 1;
let mut a = last;
loop {
let mut b = a;
a -= 1;
if self[b] < self[a] {
b = last;
while self[b] >= self[a] {
b -= 1;
}
self.swap(a, b);
self[a+1..].reverse();
return true;
}
if a == 0 {
self.reverse();
return false;
}
}
}
fn apply_permutation(&mut self, perm: &mut [isize]) {
assert_eq!(self.len(), perm.len());
assert!(self.len() < isize::max_value() as usize);
for i in 0..self.len() as isize {
let mut c = perm[i as usize];
if c < 0 {
perm[i as usize] = !c;
} else if i != c {
loop {
let n = perm[c as usize];
self.swap(c as usize, n as usize);
perm[c as usize] = !n;
c = n;
if i == c { break; }
}
}
}
}
fn apply_inverse_permutation(&mut self, perm: &mut [isize]) {
assert_eq!(self.len(), perm.len());
assert!(self.len() < isize::max_value() as usize);
for i in 0..self.len() as isize {
let mut c = perm[i as usize];
if c < 0 {
perm[i as usize] = !c;
} else if i != c {
loop {
self.swap(c as usize, i as usize);
let n = perm[c as usize];
perm[c as usize] = !n;
c = n;
if i == c { break; }
}
}
}
}
}
pub trait Ext2 {
/// Transforms the slice in the inverse permutation.
///
/// # Panics
///
/// This function panics if any value in `self` is not in `0..self.len()`.
///
/// # Example:
///
/// ```
/// # use superslice::*;
/// let mut p = [1, 3, 2, 0];
/// p.invert_permutation();
/// assert_eq!(p, [3, 0, 2, 1]);
fn invert_permutation(&mut self);
}
impl Ext2 for [isize] {
fn invert_permutation(&mut self) {
assert!(self.len() < isize::max_value() as usize);
for i in 0..self.len() as isize {
let mut c = self[i as usize];
if c < 0 {
self[i as usize] = !c;
} else if i != c {
let mut n = i;
loop {
let t = self[c as usize];
self[c as usize] = !n;
n = c;
c = t;
if c == i {
self[i as usize] = n;
break;
}
}
}
}
}
}