結果

問題 No.777 再帰的ケーキ
ユーザー ngtkana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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))
}
}
// }}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0