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::>(); let mut v = vec![0; values.len()]; let mut seg = SegmentTree::::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 { _phantom: std::marker::PhantomData, } impl Monoid for Reverse { 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 { len: usize, offset: usize, tree: Vec, } impl SegmentTree { 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 { 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) -> 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 From for SegmentTree 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 { 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 ClampRange for T where T: RangeBounds, {} } }