結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2023-04-20 11:45:57 |
言語 | Rust (1.83.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
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) -> usizewhereO::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>whereO::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>whereO::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>whereO::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>whereO::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>whereO::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>whereO::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) -> TwhereT: 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) -> usizewhereO::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>whereO::Summary: Clone,{fn clone(&self) -> Self {Self(self.0.clone())}}impl<T: PartialEq, O: Op<Value = T>> PartialEq for RbTree<T, O>whereO::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>whereO::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) -> usizewhereT: Ord;fn upper_bound(&self, x: &T) -> usizewhereT: 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) -> usizewhereT: Ord,{lower_bound(self, x)}fn upper_bound(&self, x: &T) -> usizewhereT: 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))}}// }}}