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

• 問題: No.777 再帰的ケーキ
• ユーザー: ngtkana
• 提出日時: 2023-04-20 13:53:26
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 178 ms / 2,000 ms
• コード長: 15,390 bytes
• コンパイル時間: 3,406 ms
• コンパイル使用メモリ: 174,592 KB
• 実行使用メモリ: 13,824 KB
• 最終ジャッジ日時: 2024-04-23 12:16:32
• 合計ジャッジ時間: 5,516 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 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	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 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	2 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	177 ms; 13,788 KB
testcase_29	AC	170 ms; 13,784 KB
testcase_30	AC	178 ms; 13,676 KB
testcase_31	AC	177 ms; 13,800 KB
testcase_32	AC	89 ms; 13,696 KB
testcase_33	AC	41 ms; 9,788 KB
testcase_34	AC	55 ms; 13,824 KB
testcase_35	AC	159 ms; 13,676 KB
testcase_36	AC	88 ms; 13,696 KB

ソースコード

use crate::segtree::Segtree;
use segtree::Ops;
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::<Segtree<O>>();
    for &[_, b, c] in &abc {
        let b = b_sorted.lower_bound(&b);
        let value = dp[b].max(c + dp.fold(..b));
        change_max!(&mut *dp.entry(b), value);
    }
    let ans = dp.fold(..);
    println!("{}", ans);
}

enum O {}
impl Ops for O {
    type Value = u64;
    fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value {
        (*lhs).max(*rhs)
    }
    fn identity() -> Self::Value {
        0
    }
}

// cmpmore {{{
#[allow(dead_code)]
mod cmpmore {
    pub fn change_min<T: PartialOrd>(lhs: &mut T, rhs: T) {
        if *lhs > rhs {
            *lhs = rhs;
        }
    }
    pub fn change_max<T: PartialOrd>(lhs: &mut T, rhs: T) {
        if *lhs < rhs {
            *lhs = rhs;
        }
    }
    #[macro_export]
    macro_rules! change_min {
        ($lhs:expr, $rhs:expr) => {
            let rhs = $rhs;
            let lhs = $lhs;
            $crate::cmpmore::change_min(lhs, rhs);
        };
    }
    #[macro_export]
    macro_rules! change_max {
        ($lhs:expr, $rhs:expr) => {
            let rhs = $rhs;
            let lhs = $lhs;
            $crate::cmpmore::change_max(lhs, rhs);
        };
    }
    pub trait CmpMore: PartialOrd + Sized {
        fn change_min(&mut self, rhs: Self) {
            change_min(self, rhs)
        }
        fn change_max(&mut self, rhs: Self) {
            change_max(self, rhs)
        }
    }
    impl<T: PartialOrd + Sized> CmpMore for T {}
}
// }}}
// segtree {{{
#[allow(dead_code)]
mod segtree {
    use std::{
        collections::VecDeque,
        fmt::Debug,
        iter::{repeat_with, FromIterator},
        ops::{Bound, Deref, DerefMut, Index, Range, RangeBounds},
        slice::SliceIndex,
    };
    // 演算
    pub trait Ops {
        type Value: Debug + Default;
        fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value;
        fn identity() -> Self::Value;
    }
    // 本体
    pub struct Segtree<O: Ops> {
        table: Box<[O::Value]>,
    }
    impl<O: Ops> Segtree<O> {
        pub fn new<
            I: ExactSizeIterator<Item = O::Value>,
            T: IntoIterator<Item = O::Value, IntoIter = I>,
        >(
            iter: T,
        ) -> Self {
            let iter = iter.into_iter();
            let n = iter.len();
            let mut table = repeat_with(O::Value::default).take(n).collect::<Vec<_>>();
            table.extend(iter);
            (1..n)
                .rev()
                .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1]));
            let table = table.into_boxed_slice();
            Self { table }
        }
        pub fn is_empty(&self) -> bool {
            self.table.is_empty()
        }
        pub fn len(&self) -> usize {
            self.table.len() / 2
        }
        pub fn fold(&self, range: impl RangeBounds<usize>) -> O::Value {
            let mut left = O::identity();
            let mut right = O::identity();
            let Range { mut start, mut end } = into_slice_range(self.len(), range);
            if end < start {
                segtree_index_order_fail(start, end);
            }
            if self.len() < end {
                segtree_end_index_len_fail(end, self.len());
            }
            start += self.len();
            end += self.len();
            while start != end {
                if start % 2 == 1 {
                    left = O::op(&left, &self.table[start]);
                    start += 1;
                }
                if end % 2 == 1 {
                    end -= 1;
                    right = O::op(&self.table[end], &right);
                }
                start /= 2;
                end /= 2;
            }
            O::op(&left, &right)
        }
        pub fn max_right(
            &self,
            range: impl RangeBounds<usize>,
            mut pred: impl FnMut(&O::Value) -> bool,
        ) -> usize {
            let Range { mut start, mut end } = into_slice_range(self.len(), range);
            if start == end {
                start
            } else {
                start += self.len();
                end += self.len();
                let orig_end = end;
                let mut crr = O::identity();
                let mut shift = 0;
                while start != end {
                    if start % 2 == 1 {
                        let nxt = O::op(&crr, &self.table[start]);
                        if !pred(&nxt) {
                            return self.max_right_subtree(crr, start, pred);
                        }
                        crr = nxt;
                        start += 1;
                    }
                    start /= 2;
                    end /= 2;
                    shift += 1;
                }
                for p in (0..shift).rev() {
                    let end = (orig_end >> p) - 1;
                    if end % 2 == 0 {
                        let nxt = O::op(&crr, &self.table[end]);
                        if !pred(&nxt) {
                            return self.max_right_subtree(crr, end, pred);
                        }
                        crr = nxt;
                    }
                }
                orig_end - self.len()
            }
        }
        fn max_right_subtree(
            &self,
            mut crr: O::Value,
            mut root: usize,
            mut pred: impl FnMut(&O::Value) -> bool,
        ) -> usize {
            while root < self.len() {
                let nxt = O::op(&crr, &self.table[root * 2]);
                root = if pred(&nxt) {
                    crr = nxt;
                    root * 2 + 1
                } else {
                    root * 2
                };
            }
            root - self.len()
        }
        pub fn max_left(
            &self,
            range: impl RangeBounds<usize>,
            mut pred: impl FnMut(&O::Value) -> bool,
        ) -> usize {
            let Range { mut start, mut end } = into_slice_range(self.len(), range);
            if start == end {
                start
            } else {
                start += self.len();
                end += self.len();
                let orig_start_m1 = start - 1;
                let mut crr = O::identity();
                let mut shift = 0;
                while start != end {
                    if end % 2 == 1 {
                        end -= 1;
                        let nxt = O::op(&self.table[end], &crr);
                        if !pred(&nxt) {
                            return self.max_left_subtree(crr, end, pred);
                        }
                        crr = nxt;
                    }
                    start = (start + 1) >> 1;
                    end >>= 1;
                    shift += 1;
                }
                for p in (0..shift).rev() {
                    let start = (orig_start_m1 >> p) + 1;
                    if start % 2 == 1 {
                        let nxt = O::op(&self.table[start], &crr);
                        if !pred(&nxt) {
                            return self.max_left_subtree(crr, start, pred);
                        }
                        crr = nxt;
                    }
                }
                orig_start_m1 + 1 - self.len()
            }
        }
        fn max_left_subtree(
            &self,
            mut crr: O::Value,
            mut root: usize,
            mut pred: impl FnMut(&O::Value) -> bool,
        ) -> usize {
            while root < self.len() {
                let nxt = O::op(&self.table[root * 2 + 1], &crr);
                root = if pred(&nxt) {
                    crr = nxt;
                    root * 2
                } else {
                    root * 2 + 1
                };
            }
            root + 1 - self.len()
        }
        pub fn entry(&mut self, idx: usize) -> Entry<'_, O> {
            Entry { idx, seg: self }
        }
        pub fn as_slice(&self) -> &[O::Value] {
            self.as_ref()
        }
        pub fn as_slice_mut(&mut self) -> &mut [O::Value] {
            self.as_mut()
        }
    }
    // 要素アクセス
    impl<O: Ops, Idx: SliceIndex<[O::Value], Output = O::Value>> Index<Idx> for Segtree<O> {
        type Output = O::Value;
        fn index(&self, index: Idx) -> &Self::Output {
            &self.as_slice()[index]
        }
    }
    pub struct Entry<'a, O: Ops> {
        idx: usize,
        seg: &'a mut Segtree<O>,
    }
    impl<'a, O: Ops> Drop for Entry<'a, O> {
        fn drop(&mut self) {
            self.idx += self.seg.len();
            self.idx /= 2;
            while self.idx != 0 {
                self.seg.table[self.idx] = O::op(
                    &self.seg.table[2 * self.idx],
                    &self.seg.table[2 * self.idx + 1],
                );
                self.idx /= 2;
            }
        }
    }
    impl<O: Ops> Deref for Entry<'_, O> {
        type Target = O::Value;
        fn deref(&self) -> &Self::Target {
            &self.seg.as_slice()[self.idx]
        }
    }
    impl<O: Ops> DerefMut for Entry<'_, O> {
        fn deref_mut(&mut self) -> &mut Self::Target {
            &mut self.seg.as_slice_mut()[self.idx]
        }
    }
    // 変換
    impl<O: Ops> From<Vec<O::Value>> for Segtree<O> {
        fn from(v: Vec<O::Value>) -> Self {
            Self::new(v)
        }
    }
    impl<O: Ops> FromIterator<O::Value> for Segtree<O> {
        fn from_iter<T: IntoIterator<Item = O::Value>>(iter: T) -> Self {
            let mut v = iter.into_iter().collect::<VecDeque<_>>();
            let n = v.len();
            let mut table = repeat_with(O::Value::default)
                .take(n)
                .collect::<VecDeque<_>>();
            table.append(&mut v);
            (1..n)
                .rev()
                .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1]));
            let table = Vec::from(table).into_boxed_slice();
            Self { table }
        }
    }
    impl<O: Ops> AsRef<[O::Value]> for Segtree<O> {
        fn as_ref(&self) -> &[O::Value] {
            &self.table[self.len()..]
        }
    }
    impl<O: Ops> AsMut<[O::Value]> for Segtree<O> {
        fn as_mut(&mut self) -> &mut [O::Value] {
            let n = self.len();
            &mut self.table[n..]
        }
    }
    // フォーマット
    impl<O: Ops> Debug for Segtree<O> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            self.as_slice().fmt(f)
        }
    }
    // プライベート - RangeBounds 関連
    fn into_slice_range(len: usize, range: impl RangeBounds<usize>) -> Range<usize> {
        #[allow(clippy::redundant_closure)]
        let start = match range.start_bound() {
            Bound::Included(&start) => start,
            Bound::Excluded(&start) => start
                .checked_add(1)
                .unwrap_or_else(|| slice_start_index_overflow_fail()),
            Bound::Unbounded => 0,
        };
        #[allow(clippy::redundant_closure)]
        let end = match range.end_bound() {
            Bound::Included(&end) => end
                .checked_add(1)
                .unwrap_or_else(|| slice_end_index_overflow_fail()),
            Bound::Excluded(&end) => end,
            Bound::Unbounded => len,
        };
        start..end
    }
    fn segtree_end_index_len_fail(index: usize, len: usize) -> ! {
        panic!(
            "range end index {} out of range for segtree of length {}",
            index, len
        );
    }
    fn segtree_index_order_fail(index: usize, end: usize) -> ! {
        panic!("segtree index starts at {} but ends at {}", index, end);
    }
    fn slice_start_index_overflow_fail() -> ! {
        panic!("attempted to index slice from after maximum usize");
    }
    fn slice_end_index_overflow_fail() -> ! {
        panic!("attempted to index slice up to maximum usize");
    }
    // テスト
}
// }}}
// 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))
    }
}
// }}}