#860875 (Rust) No.777 再帰的ケーキ

提出ソース
結果

問題	No.777 再帰的ケーキ
ユーザー	ngtkana
提出日時	2023-04-20 11:45:57
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	1,598 ms / 2,000 ms
コード長	22,711 bytes
コンパイル時間	14,866 ms
コンパイル使用メモリ	384,464 KB
実行使用メモリ	23,912 KB
最終ジャッジ日時	2024-10-15 10:44:17
合計ジャッジ時間	27,064 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	1 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	7 ms 5,248 KB
testcase_22	AC	7 ms 5,248 KB
testcase_23	AC	6 ms 5,248 KB
testcase_24	AC	4 ms 5,248 KB
testcase_25	AC	8 ms 5,248 KB
testcase_26	AC	8 ms 5,248 KB
testcase_27	AC	5 ms 5,248 KB
testcase_28	AC	1,520 ms 23,772 KB
testcase_29	AC	1,524 ms 23,900 KB
testcase_30	AC	1,550 ms 23,764 KB
testcase_31	AC	1,598 ms 23,912 KB
testcase_32	AC	726 ms 23,780 KB
testcase_33	AC	698 ms 16,444 KB
testcase_34	AC	621 ms 23,680 KB
testcase_35	AC	1,320 ms 23,744 KB
testcase_36	AC	717 ms 23,708 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
use rbtree::{Op, RbTree};
use slicemore::SliceMore;
use std::{cmp::Reverse, convert::TryFrom, io::stdin, iter::repeat_with};

fn main() {
    let stdin = stdin();
    let mut stdin = stdin.lines().map(Result::unwrap);
    let n = stdin.next().unwrap().parse::<usize>().unwrap();
    let mut abc = repeat_with(|| {
        <[_; 3]>::try_from(
            stdin
                .next()
                .unwrap()
                .split_whitespace()
                .map(|x| x.parse::<u64>().unwrap())
                .collect::<Vec<_>>(),
        )
        .unwrap()
    })
    .take(n)
    .collect::<Vec<_>>();
    abc.sort_by_key(|&[a, b, _]| (a, Reverse(b)));
    let mut b_sorted = abc.iter().map(|&[_, b, _]| b).collect::<Vec<_>>();
    b_sorted.sort();
    let mut dp = vec![0; n].into_iter().collect::<RbTree<_, O>>();
    for &[_, b, c] in &abc {
        let b = b_sorted.lower_bound(&b);
        let value = dp.get(b).max(c + dp.fold(..b).unwrap_or(0));
        dp.delete(b);
        dp.insert(b, value);
    }
    let ans = dp.fold(..).unwrap();
    println!("{}", ans);
}

enum O {}
impl Op for O {
    type Summary = u64;
    type Value = u64;
    fn summarize(value: &Self::Value) -> Self::Summary {
        *value
    }
    fn op(lhs: Self::Summary, rhs: Self::Summary) -> Self::Summary {
        lhs.max(rhs)
    }
}

// rbtree {{{
#[allow(dead_code)]
mod rbtree {
    #![warn(missing_docs)]
    mod nonempty {
        use {
            super::{Nop, Op},
            std::{
                cmp::Ordering,
                hash::{Hash, Hasher},
                marker::PhantomData,
                mem::swap,
            },
        };
        pub enum Nonempty<T, O: Op<Value = T> = Nop<T>> {
            Nil(Nil<T>),
            Internal(Box<Internal<T, O>>),
        }
        #[derive(Clone, Debug, Default, Hash, PartialEq, Eq, Copy)]
        pub struct Nil<T>(pub T);
        pub struct Internal<T, O: Op<Value = T>> {
            pub left: Nonempty<T, O>,
            pub right: Nonempty<T, O>,
            pub height: usize,
            pub len: usize,
            pub summary: O::Summary,
            pub __marker: PhantomData<fn(O) -> O>,
        }
        impl<T, O: Op<Value = T>> Internal<T, O> {
            pub fn update(&mut self) {
                self.len = self.left.len() + self.right.len();
                self.summary = O::op(self.left.summary(), self.right.summary());
            }
        }
        impl<T, O: Op<Value = T>> Nonempty<T, O> {
            pub fn len(&self) -> usize {
                match self {
                    Self::Nil(_) => 1,
                    Self::Internal(node) => node.len,
                }
            }
            pub fn not_all_partition_point<F>(&self, init: Option<O::Summary>, f: F) -> usize
            where
                O::Summary: Clone,
                F: Fn(&O::Summary) -> bool,
            {
                match self {
                    Self::Nil(Nil(x)) => {
                        let x = O::summarize(x);
                        let init = match init {
                            None => x,
                            Some(init) => O::op(init, x),
                        };
                        if f(&init) {
                            1
                        } else {
                            0
                        }
                    }
                    Self::Internal(node) => {
                        let linit = match init.clone() {
                            None => node.left.summary(),
                            Some(init) => O::op(init, node.left.summary()),
                        };
                        if f(&linit) {
                            node.left.len() + node.right.not_all_partition_point(Some(linit), f)
                        } else {
                            node.left.not_all_partition_point(init, f)
                        }
                    }
                }
            }
            pub fn fold(&self, start: usize, end: usize) -> O::Summary {
                debug_assert!(start < end && end <= self.len());
                match self {
                    Self::Nil(Nil(x)) => O::summarize(x),
                    Self::Internal(node) => {
                        let lsize = node.left.len();
                        if start == 0 && end == self.len() {
                            node.summary.clone()
                        } else if end <= lsize {
                            node.left.fold(start, end)
                        } else if lsize <= start {
                            node.right.fold(start - lsize, end - lsize)
                        } else {
                            O::op(
                                node.left.fold(start, lsize),
                                node.right.fold(0, end - lsize),
                            )
                        }
                    }
                }
            }
            pub fn split(self, i: usize) -> [Self; 2] {
                let node = self.into_node().unwrap();
                let left_len = node.left.len();
                match i.cmp(&left_len) {
                    Ordering::Equal => [node.left, node.right],
                    Ordering::Less => {
                        let [l, r] = node.left.split(i);
                        [l, Self::merge(r, node.right)]
                    }
                    Ordering::Greater => {
                        let [l, r] = node.right.split(i - left_len);
                        [Self::merge(node.left, l), r]
                    }
                }
            }
            pub fn merge(mut lhs: Self, mut rhs: Self) -> Self {
                let h = lhs.height();
                match h.cmp(&rhs.height()) {
                    Ordering::Equal => Self::from_children(lhs, rhs, h + 1),
                    Ordering::Less => {
                        rhs.merge_front(lhs);
                        rhs
                    }
                    Ordering::Greater => {
                        lhs.merge_back(rhs);
                        lhs
                    }
                }
            }
            pub fn merge_front(&mut self, other: Self) {
                let h = self.height();
                if other.height() == self.node().unwrap().left.height() {
                    let Internal { left, .. } = self.node_mut().unwrap();
                    replace_with(left, |x| Self::from_children(other, x, h));
                } else {
                    self.node_mut().unwrap().left.merge_front(other);
                }
                if self.node().unwrap().left.node().unwrap().left.height() == h {
                    if self.node().unwrap().right.height() == h {
                        self.node_mut().unwrap().height += 1;
                    } else {
                        let Internal { left, right, .. } = self.node_mut().unwrap();
                        swap(left, right);
                        let l = left;
                        let Internal { left, right, .. } = right.node_mut().unwrap();
                        swap(l, left);
                        swap(left, right);
                        self.node_mut().unwrap().right.node_mut().unwrap().update();
                    }
                }
                self.node_mut().unwrap().update();
            }
            pub fn merge_back(&mut self, other: Self) {
                let h = self.height();
                if other.height() == self.node().unwrap().right.height() {
                    let Internal { right, .. } = self.node_mut().unwrap();
                    replace_with(right, |x| Self::from_children(x, other, h));
                } else {
                    self.node_mut().unwrap().right.merge_back(other);
                }
                if self.node().unwrap().right.node().unwrap().right.height() == h {
                    if self.node().unwrap().left.height() == h {
                        self.node_mut().unwrap().height += 1;
                    } else {
                        let Internal { left, right, .. } = self.node_mut().unwrap();
                        swap(left, right);
                        let r = right;
                        let Internal { left, right, .. } = left.node_mut().unwrap();
                        swap(right, r);
                        swap(left, right);
                        self.node_mut().unwrap().left.node_mut().unwrap().update();
                    }
                }
                self.node_mut().unwrap().update();
            }
            pub fn node(&self) -> Option<&Internal<T, O>> {
                match self {
                    Self::Nil(_) => None,
                    Self::Internal(node) => Some(node),
                }
            }
            pub fn node_mut(&mut self) -> Option<&mut Internal<T, O>> {
                match self {
                    Self::Nil(_) => None,
                    Self::Internal(node) => Some(node),
                }
            }
            pub fn summary(&self) -> O::Summary {
                match self {
                    Self::Nil(Nil(x)) => O::summarize(x),
                    Self::Internal(node) => node.summary.clone(),
                }
            }
            fn into_node(self) -> Option<Internal<T, O>> {
                match self {
                    Self::Nil(_) => None,
                    Self::Internal(node) => Some(*node),
                }
            }
            #[allow(clippy::wrong_self_convention)]
            fn from_children(lhs: Self, rhs: Self, height: usize) -> Self {
                Self::Internal(Box::new(Internal {
                    len: lhs.len() + rhs.len(),
                    summary: O::op(lhs.summary(), rhs.summary()),
                    height,
                    left: lhs,
                    right: rhs,
                    __marker: PhantomData,
                }))
            }
            fn height(&self) -> usize {
                match self {
                    Self::Nil(_) => 0,
                    Self::Internal(node) => node.height,
                }
            }
        }
        fn replace_with<T, F: FnOnce(T) -> T>(dest: &mut T, f: F) {
            unsafe { std::ptr::write(dest, f(std::ptr::read(dest))) }
        }
        impl<T: Clone, O: Op<Value = T>> Clone for Nonempty<T, O>
        where
            O::Summary: Clone,
        {
            fn clone(&self) -> Self {
                match self {
                    Self::Nil(x) => Self::Nil(x.clone()),
                    Self::Internal(x) => Self::Internal(x.clone()),
                }
            }
        }
        impl<T: Clone, O: Op<Value = T>> Clone for Internal<T, O>
        where
            O::Summary: Clone,
        {
            fn clone(&self) -> Self {
                Self {
                    left: self.left.clone(),
                    right: self.right.clone(),
                    height: self.height,
                    len: self.len,
                    summary: self.summary.clone(),
                    __marker: self.__marker,
                }
            }
        }
        impl<T: PartialEq, O: Op<Value = T>> PartialEq for Nonempty<T, O>
        where
            O::Summary: PartialEq,
        {
            fn eq(&self, other: &Self) -> bool {
                match [self, other] {
                    [Self::Nil(x), Self::Nil(y)] => x.eq(y),
                    [Self::Internal(x), Self::Internal(y)] => x.eq(y),
                    _ => false,
                }
            }
        }
        impl<T: PartialEq, O: Op<Value = T>> PartialEq for Internal<T, O>
        where
            O::Summary: PartialEq,
        {
            fn eq(&self, other: &Self) -> bool {
                self.left.eq(&other.left)
                    && self.right.eq(&other.right)
                    && self.height.eq(&other.height)
                    && self.len.eq(&other.len)
                    && self.summary.eq(&other.summary)
            }
        }
        impl<T: Hash, O: Op<Value = T>> Hash for Nonempty<T, O>
        where
            O::Summary: Hash,
        {
            fn hash<H: Hasher>(&self, state: &mut H) {
                match self {
                    Self::Nil(x) => x.hash(state),
                    Self::Internal(x) => x.hash(state),
                }
            }
        }
        impl<T: Hash, O: Op<Value = T>> Hash for Internal<T, O>
        where
            O::Summary: Hash,
        {
            fn hash<H: Hasher>(&self, state: &mut H) {
                self.left.hash(state);
                self.right.hash(state);
                self.height.hash(state);
                self.len.hash(state);
                self.summary.hash(state);
            }
        }
    }
    use {
        nonempty::{Nil, Nonempty},
        std::{
            fmt::{self, Debug},
            hash::{Hash, Hasher},
            iter::FromIterator,
            marker::PhantomData,
            mem::take,
            ops::{Bound, Range, RangeBounds},
        },
    };
    pub struct RbTree<T, O: Op<Value = T> = Nop<T>>(Option<Nonempty<T, O>>);
    pub trait Op {
        type Value;
        type Summary: Clone;
        fn summarize(value: &Self::Value) -> Self::Summary;
        fn op(lhs: Self::Summary, rhs: Self::Summary) -> Self::Summary;
    }
    pub struct Nop<T> {
        __marker: PhantomData<fn(T) -> T>,
    }
    impl<T> Op for Nop<T> {
        type Value = T;
        type Summary = ();
        fn summarize(_value: &Self::Value) -> Self::Summary {}
        fn op(_lhs: Self::Summary, _rhs: Self::Summary) -> Self::Summary {}
    }
    impl<A, O: Op<Value = A>> FromIterator<A> for RbTree<A, O> {
        fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
            let mut nodes = iter.into_iter().map(Self::singleton).collect::<Vec<_>>();
            if nodes.is_empty() {
                return Self::default();
            }
            let mut step = 1;
            while step < nodes.len() {
                for i in (0..nodes.len() - step).step_by(2 * step) {
                    nodes[i] = Self::merge(take(&mut nodes[i]), take(&mut nodes[i + step]));
                }
                step *= 2;
            }
            take(&mut nodes[0])
        }
    }
    pub struct Iter<'a, T, O: Op<Value = T>>(Vec<&'a Nonempty<T, O>>);
    impl<'a, T, O: Op<Value = T>> Iterator for Iter<'a, T, O> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> {
            loop {
                match self.0.pop() {
                    None => return None,
                    Some(Nonempty::Nil(Nil(x))) => return Some(x),
                    Some(Nonempty::Internal(node)) => {
                        self.0.push(&node.right);
                        self.0.push(&node.left);
                    }
                }
            }
        }
    }
    impl<T, O: Op<Value = T>> RbTree<T, O> {
        pub fn new() -> Self {
            Self(None)
        }
        pub fn is_empty(&self) -> bool {
            self.0.is_none()
        }
        pub fn len(&self) -> usize {
            match &self.0 {
                None => 0,
                Some(node) => node.len(),
            }
        }
        pub fn iter(&self) -> Iter<'_, T, O> {
            Iter(match &self.0 {
                None => Vec::new(),
                Some(node) => vec![node],
            })
        }
        pub fn get(&mut self, i: usize) -> T
        where
            T: Copy,
        {
            assert!((0..self.len()).contains(&i));
            let root = take(&mut self.0).unwrap();
            let [l, cr] = Self(Some(root)).split(i);
            let [c, r] = cr.split(1);
            let res = match c.0.as_ref().unwrap() {
                Nonempty::Nil(nil) => nil.0,
                Nonempty::Internal(_) => unreachable!(),
            };
            *self = Self::merge(Self::merge(l, c), r);
            res
        }
        pub fn partition_point<F>(&self, f: F) -> usize
        where
            O::Summary: Clone,
            F: Fn(&O::Summary) -> bool,
        {
            match self.0.as_ref() {
                None => 0,
                Some(nonempty) => {
                    if f(&nonempty.summary()) {
                        self.len()
                    } else {
                        nonempty.not_all_partition_point(None, f)
                    }
                }
            }
        }
        pub fn fold(&self, range: impl RangeBounds<usize>) -> Option<O::Summary> {
            let Range { start, end } = open(range, self.len());
            assert!(start <= end && end <= self.len());
            if start == end {
                None
            } else {
                Some(self.0.as_ref().unwrap().fold(start, end))
            }
        }
        pub fn singleton(x: T) -> Self {
            Self(Some(Nonempty::Nil(Nil(x))))
        }
        pub fn push_front(&mut self, x: T) {
            *self = Self::merge(Self::singleton(x), take(self));
        }
        pub fn push_back(&mut self, x: T) {
            *self = Self::merge(take(self), Self::singleton(x));
        }
        pub fn insert(&mut self, i: usize, x: T) {
            assert!((0..=self.len()).contains(&i));
            let [l, r] = take(self).split(i);
            *self = Self::merge3(l, Self::singleton(x), r);
        }
        pub fn delete(&mut self, i: usize) -> T {
            assert!((0..self.len()).contains(&i));
            let [l, c, r] = take(self).split3(i, i + 1);
            *self = Self::merge(l, r);
            match c.0 {
                Some(Nonempty::Internal(_)) | None => unreachable!(),
                Some(Nonempty::Nil(Nil(value))) => value,
            }
        }
        pub fn merge(lhs: Self, rhs: Self) -> Self {
            match [lhs.0, rhs.0] {
                [None, None] => Self(None),
                [Some(l), None] => Self(Some(l)),
                [None, Some(r)] => Self(Some(r)),
                [Some(l), Some(r)] => Self(Some(Nonempty::merge(l, r))),
            }
        }
        pub fn merge3(x: Self, y: Self, z: Self) -> Self {
            Self::merge(Self::merge(x, y), z)
        }
        pub fn split(self, i: usize) -> [Self; 2] {
            assert!((0..=self.len()).contains(&i));
            if i == 0 {
                [Self(None), self]
            } else if i == self.len() {
                [self, Self(None)]
            } else {
                let [l, r] = self.0.unwrap().split(i);
                [Self(Some(l)), Self(Some(r))]
            }
        }
        pub fn split3(self, start: usize, end: usize) -> [Self; 3] {
            let [xy, z] = self.split(end);
            let [x, y] = xy.split(start);
            [x, y, z]
        }
    }
    impl<T: Clone, O: Op<Value = T>> Clone for RbTree<T, O>
    where
        O::Summary: Clone,
    {
        fn clone(&self) -> Self {
            Self(self.0.clone())
        }
    }
    impl<T: PartialEq, O: Op<Value = T>> PartialEq for RbTree<T, O>
    where
        O::Summary: PartialEq,
    {
        fn eq(&self, other: &Self) -> bool {
            self.0.eq(&other.0)
        }
    }
    impl<T: Hash, O: Op<Value = T>> Hash for RbTree<T, O>
    where
        O::Summary: Hash,
    {
        fn hash<H: Hasher>(&self, state: &mut H) {
            self.0.hash(state);
        }
    }
    impl<T: Debug, O: Op<Value = T>> Debug for RbTree<T, O> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            f.debug_list().entries(self.iter()).finish()
        }
    }
    impl<T, O: Op<Value = T>> Default for RbTree<T, O> {
        fn default() -> Self {
            Self::new()
        }
    }
    fn open(range: impl RangeBounds<usize>, len: usize) -> Range<usize> {
        (match range.start_bound() {
            Bound::Unbounded => 0,
            Bound::Included(&x) => x,
            Bound::Excluded(&x) => x + 1,
        })..match range.end_bound() {
            Bound::Excluded(&x) => x,
            Bound::Included(&x) => x + 1,
            Bound::Unbounded => len,
        }
    }
}
// }}}
// slicemore {{{
#[allow(dead_code)]
mod slicemore {
    use std::cmp::Ordering::{self, Equal, Greater, Less};
    pub trait SliceMore<T> {
        fn partition_point<F: FnMut(&T) -> bool>(&self, pred: F) -> usize;
        fn lower_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize;
        fn upper_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize;
        fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize;
        fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize;
        fn lower_bound(&self, x: &T) -> usize
        where
            T: Ord;
        fn upper_bound(&self, x: &T) -> usize
        where
            T: Ord;
    }
    impl<T> SliceMore<T> for [T] {
        fn partition_point<F: FnMut(&T) -> bool>(&self, pred: F) -> usize {
            partition_point(self, pred)
        }
        fn lower_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize {
            lower_bound_by(self, f)
        }
        fn upper_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize {
            upper_bound_by(self, f)
        }
        fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize {
            lower_bound_by_key(self, b, f)
        }
        fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize {
            upper_bound_by_key(self, b, f)
        }
        fn lower_bound(&self, x: &T) -> usize
        where
            T: Ord,
        {
            lower_bound(self, x)
        }
        fn upper_bound(&self, x: &T) -> usize
        where
            T: Ord,
        {
            upper_bound(self, x)
        }
    }
    pub fn partition_point<T, F: FnMut(&T) -> bool>(slice: &[T], mut pred: F) -> usize {
        slice
            .binary_search_by(|x| if pred(x) { Less } else { Greater })
            .unwrap_err()
    }
    pub fn lower_bound_by<T, F: FnMut(&T) -> Ordering>(slice: &[T], mut f: F) -> usize {
        partition_point(slice, |x| matches!(f(x), Less))
    }
    pub fn upper_bound_by<T, F: FnMut(&T) -> Ordering>(slice: &[T], mut f: F) -> usize {
        partition_point(slice, |x| matches!(f(x), Less | Equal))
    }
    pub fn lower_bound_by_key<T, B: Ord, F: FnMut(&T) -> B>(slice: &[T], b: &B, mut f: F) -> usize {
        lower_bound_by(slice, |x| f(x).cmp(b))
    }
    pub fn upper_bound_by_key<T, B: Ord, F: FnMut(&T) -> B>(slice: &[T], b: &B, mut f: F) -> usize {
        upper_bound_by(slice, |x| f(x).cmp(b))
    }
    pub fn lower_bound<T: Ord>(slice: &[T], x: &T) -> usize {
        lower_bound_by(slice, |p| p.cmp(x))
    }
    pub fn upper_bound<T: Ord>(slice: &[T], x: &T) -> usize {
        upper_bound_by(slice, |p| p.cmp(x))
    }
}
// }}}
yukicoder

結果

テストケース

ソースコード
