結果
| 問題 | No.777 再帰的ケーキ |
| コンテスト | |
| ユーザー |
 urectanc
|
| 提出日時 | 2026-05-06 08:54:46 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 154 ms / 2,000 ms |
| コード長 | 8,151 bytes |
| 記録 | |
| コンパイル時間 | 2,808 ms |
| コンパイル使用メモリ | 226,220 KB |
| 実行使用メモリ | 15,660 KB |
| 最終ジャッジ日時 | 2026-05-06 08:54:58 |
| 合計ジャッジ時間 | 7,363 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 33 |
ソースコード
use std::collections::HashMap;
use itertools::Itertools;
use proconio::input;
use urectanc::{algebra::Monoid, segment_tree::SegmentTree};
fn main() {
input! {
n: usize,
mut abc: [(u32, u32, u64); n],
}
abc.sort_unstable();
let values = abc
.iter()
.map(|t| t.1)
.sorted_unstable()
.dedup()
.collect_vec();
let compress = values
.iter()
.enumerate()
.map(|(i, &x)| (x, i))
.collect::<HashMap<_, _>>();
let mut v = vec![0; values.len()];
let mut seg = SegmentTree::<Max>::from(&v);
let mut update = vec![];
for chunk in abc.chunk_by(|x, y| x.0 == y.0) {
for &(_, b, c) in chunk {
let b = compress[&b];
let cand = seg.prod(..b) + c;
if v[b] < cand {
update.push((b, cand));
}
}
for (b, cand) in update.drain(..) {
if v[b] < cand {
v[b] = cand;
seg.set(b, cand);
}
}
}
let ans = seg.prod(..);
println!("{ans}");
}
struct Max;
impl Monoid for Max {
type Elem = u64;
fn identity() -> Self::Elem {
0
}
fn op(lhs: &Self::Elem, rhs: &Self::Elem) -> Self::Elem {
*(lhs.max(rhs))
}
}
pub mod urectanc {
pub mod algebra {
pub trait Monoid {
type Elem: Clone;
fn identity() -> Self::Elem;
fn op(lhs: &Self::Elem, rhs: &Self::Elem) -> Self::Elem;
}
pub trait Group: Monoid {
fn inv(elem: &Self::Elem) -> Self::Elem;
}
pub trait MapMonoid: Monoid {
type Map: Clone;
fn identity_map() -> Self::Map;
fn apply(x: &Self::Elem, f: &Self::Map) -> Self::Elem;
fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map;
}
pub struct Reverse<M> {
_phantom: std::marker::PhantomData<M>,
}
impl<M: Monoid> Monoid for Reverse<M> {
type Elem = M::Elem;
fn identity() -> Self::Elem {
M::identity()
}
fn op(lhs: &Self::Elem, rhs: &Self::Elem) -> Self::Elem {
M::op(rhs, lhs)
}
}
}
pub mod segment_tree {
use crate::urectanc::{algebra, clamp_range};
use std::ops::RangeBounds;
use algebra::Monoid;
use clamp_range::ClampRange;
pub struct SegmentTree<M: Monoid> {
len: usize,
offset: usize,
tree: Vec<M::Elem>,
}
impl<M: Monoid> SegmentTree<M> {
pub fn new(len: usize) -> Self {
let offset = len.next_power_of_two();
let tree = vec![M::identity(); 2 * offset];
Self { len, offset, tree }
}
pub fn to_vec(&self) -> Vec<M::Elem> {
self.tree[self.offset..][..self.len].to_vec()
}
pub fn get(&self, i: usize) -> M::Elem {
self.tree[i + self.offset].clone()
}
pub fn set(&mut self, mut i: usize, val: M::Elem) {
i += self.offset;
self.tree[i] = val;
while i > 1 {
i >>= 1;
self.update(i);
}
}
pub fn prod(&self, range: impl RangeBounds<usize>) -> M::Elem {
let (mut l, mut r) = range.clamp(0, self.len);
if (l, r) == (0, self.len) {
return self.tree[1].clone();
}
(l, r) = (l + self.offset, r + self.offset);
let mut acc_l = M::identity();
let mut acc_r = M::identity();
while l < r {
if l & 1 == 1 {
acc_l = M::op(&acc_l, &self.tree[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
acc_r = M::op(&self.tree[r], &acc_r);
}
(l, r) = (l >> 1, r >> 1);
}
M::op(&acc_l, &acc_r)
}
pub fn max_right(&self, l: usize, f: impl Fn(&M::Elem) -> bool) -> usize {
let mut r = l;
let (mut i, mut width) = (r + self.offset, 1);
let mut acc = M::identity();
assert!(f(& acc));
while r + width <= self.len {
if i & 1 == 1 {
let next_acc = M::op(&acc, &self.tree[i]);
if !f(&next_acc) {
break;
}
acc = next_acc;
(r, i) = (r + width, i + 1);
}
(i, width) = (i >> 1, width << 1);
}
while width > 1 {
(i, width) = (i << 1, width >> 1);
if r + width <= self.len {
let next_acc = M::op(&acc, &self.tree[i]);
if f(&next_acc) {
acc = next_acc;
(r, i) = (r + width, i + 1);
}
}
}
r
}
pub fn min_left(&self, r: usize, f: impl Fn(&M::Elem) -> bool) -> usize {
let mut l = r;
let (mut i, mut width) = (l + self.offset, 1);
let mut acc = M::identity();
assert!(f(& acc));
while l >= width {
if i & 1 == 1 {
let next_acc = M::op(&self.tree[i - 1], &acc);
if !f(&next_acc) {
break;
}
acc = next_acc;
(l, i) = (l - width, i - 1);
}
(i, width) = (i >> 1, width << 1);
}
while width > 1 {
(i, width) = (i << 1, width >> 1);
if l >= width {
let next_acc = M::op(&self.tree[i - 1], &acc);
if f(&next_acc) {
acc = next_acc;
(l, i) = (l - width, i - 1);
}
}
}
l
}
fn update(&mut self, i: usize) {
self.tree[i] = M::op(&self.tree[2 * i], &self.tree[2 * i + 1]);
}
}
impl<M, T> From<T> for SegmentTree<M>
where
M: Monoid,
T: AsRef<[M::Elem]>,
{
fn from(value: T) -> Self {
let a = value.as_ref();
let len = a.len();
let offset = len.next_power_of_two();
let mut tree = vec![M::identity(); 2 * offset];
tree[offset..][..len].clone_from_slice(a);
let mut segtree = Self { len, offset, tree };
for i in (1..offset).rev() {
segtree.update(i);
}
segtree
}
}
}
pub mod clamp_range {
use std::ops::{Bound, RangeBounds};
pub trait ClampRange: RangeBounds<usize> {
fn clamp(&self, l: usize, r: usize) -> (usize, usize) {
assert!(l <= r);
let start = match self.start_bound() {
Bound::Included(&l) => l,
Bound::Excluded(&l) => l + 1,
Bound::Unbounded => l,
}
.clamp(l, r);
let end = match self.end_bound() {
Bound::Included(&r) => r + 1,
Bound::Excluded(&r) => r,
Bound::Unbounded => r,
}
.clamp(l, r);
(start.min(end), end)
}
}
impl<T: ?Sized> ClampRange for T
where
T: RangeBounds<usize>,
{}
}
}