結果
| 問題 | No.3424 Shooting Game |
| コンテスト | |
| ユーザー |
 chiaoi
|
| 提出日時 | 2026-01-11 15:01:00 |
| 言語 | Rust (1.92.0 + proconio + num) |
| 結果 |
AC
|
| 実行時間 | 183 ms / 2,000 ms |
| コード長 | 9,544 bytes |
| 記録 | |
| コンパイル時間 | 22,857 ms |
| コンパイル使用メモリ | 414,216 KB |
| 実行使用メモリ | 14,428 KB |
| 最終ジャッジ日時 | 2026-01-11 17:23:12 |
| 合計ジャッジ時間 | 25,451 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 11 |
ソースコード
use proconio::input;
#[allow(unused)]
use proconio::marker::*;
#[allow(unused)]
use std::collections::*;
fn main() {
input! {
n: usize,
t: usize,
mut lrp: [(usize, usize, u64); n],
};
let mut segtree = LazySegTree::<O>::new(400_000);
for &(l, r, p) in &lrp {
segtree.range_apply(l..=r, &p);
}
let mut dp = vec![0; 400_000 + 1];
for i in t..=400_000 {
dp[i] = dp[i - 1].max(dp[i - t] + segtree.range_fold(i - t..=i - t));
}
println!("{}", dp.last().unwrap());
}
enum O {}
impl MonoidAction for O {
type S = u64;
type F = u64;
fn identity_s() -> Self::S {
0
}
fn identity_f() -> Self::F {
0
}
fn op_s(a: &Self::S, b: &Self::S) -> Self::S {
*a.max(b)
}
fn op_f(a: &Self::F, b: &Self::F) -> Self::F {
*a.max(b)
}
fn apply(x: &mut Self::S, f: &Self::F) {
if *x < *f {
*x = *f;
}
}
}
/// A trait representing a *monoid action*.
///
/// A monoid action consists of:
/// - A value set `S` (the associated type [`Self::S`])
/// - An associative binary operation in value ([`Self::op_s`])
/// - An identity element in value ([`Self::identity_s`])
/// - An operator set `F` (the associated type [`Self::F`])
/// - An associative binary operation in operator ([`Self::op_f`])
/// - An identity element in operator ([`Self::identity_f`])
pub trait MonoidAction {
/// The underlying value type.
type S;
/// The underlying operator type.
type F: Clone;
/// Returns the identity element of the value set `S`.
///
/// The identity element `e` satisfies `op_s(&a, &e) = op(&e, &a) = a` for all `a` in `S`.
fn identity_s() -> Self::S;
/// Returns the identity element of the operator set `F`.
///
/// The identity element `e` satisfies `op_f(&a, &e) = op(&e, &a) = a` for all `a` in `S`.
fn identity_f() -> Self::F;
/// Returns the result of binary operation on `a` and `b` in `S`.
///
/// This operation must be associative:
/// `op_s(&op_s(&a, &b), &c) = op_s(&a, &op_s(&b, &c))` for all `a, b, c` in `S`.
fn op_s(a: &Self::S, b: &Self::S) -> Self::S;
/// Returns the result of binary operation on `a` and `b` in `F`.
///
/// This operation must be associative:
/// `op_f(&op_f(&a, &b), &c) = op_f(&a, &op_f(&b, &c))` for all `a, b, c` in `F`.
fn op_f(a: &Self::F, b: &Self::F) -> Self::F;
/// Applies an operator to data in-place.
///
/// This operation must satisfy the homomorphism property.
fn apply(x: &mut Self::S, f: &Self::F);
}
/// A *Lazy Segment Tree* that supports range queries and range updates.
///
/// The time complexity of operations depends on the cost of the monoid action operations:
/// If these operations take `O(1)` time, run in `O(log n)` time.
///
/// # Type Parameters
///
/// - `T`: A type implementing the [`MonoidAction`] trait.
#[derive(Debug, Clone)]
pub struct LazySegTree<T: MonoidAction> {
/// The number of the sequence which is managed by this.
n: usize,
/// The capacity of the underlying array (next power of two >= n)
m: usize,
/// Internal data array of size `2 * m`.
/// Indices `[m, m + n)` store the actual data.
/// Indices `[1, m)` store aggregated results.
/// Index `0` is unused.
data: Box<[T::S]>,
/// Internal lazy propagation array of size `2 * m`.
/// - Stores pending operators that need to be propagated to children.
/// - `func[k]` is the operator pending for the subtree rooted at node `k`.
func: Box<[T::F]>,
}
impl<T: MonoidAction> LazySegTree<T> {
/// Creates a new Lazy Segment Tree with identity sequence with length `n`,
/// `a_i == T::identity_s()` for all `0 <= i < n`.
///
/// ## Parameters
///
/// - `n`: Length of sequence.
///
/// ## complexity
///
/// `O(n)`
pub fn new(n: usize) -> Self {
let m = n.next_power_of_two();
Self {
n,
m,
data: std::iter::repeat_with(T::identity_s).take(2 * m).collect(),
func: vec![T::identity_f(); 2 * m].into_boxed_slice(),
}
}
/// Calculates the monoid operation over a range.
///
/// ## Parameters
///
/// - `range`: The range of intervals. This must be `RangeBounds<usize>`.
///
/// ## Returns
///
/// If sequence managed by this is `a` and `range` is `[l, r)`,
/// returns `a[l] * a[l + 1] * ... * a[r - 1]`.
///
/// ## Complexity
///
/// `O(log n)`
#[inline]
pub fn range_fold(&mut self, range: impl std::ops::RangeBounds<usize>) -> T::S {
use std::ops::Bound::{Excluded, Included, Unbounded};
let mut l = match range.start_bound() {
Unbounded => 0,
Included(x) => *x,
Excluded(x) => x + 1,
} + self.m;
let mut r = match range.end_bound() {
Unbounded => self.n,
Included(x) => x + 1,
Excluded(x) => *x,
} + self.m;
debug_assert!(
l <= r,
"invalid range: start {} must be smaller than or equal to end {}",
l - self.m,
r - self.m
);
debug_assert!(
r <= self.n + self.m,
"invalid range: range end {} must be smaller than length {}",
r - self.m,
self.n
);
for k in (1..=self.m.trailing_zeros()).rev() {
if (l >> k) << k != l {
self.push(l >> k);
}
if (r >> k) << k != r {
self.push((r - 1) >> k);
}
}
let mut left = T::identity_s();
let mut right = T::identity_s();
while l < r {
if l & 1 == 1 {
left = T::op_s(&left, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
right = T::op_s(&self.data[r], &right);
}
l >>= 1;
r >>= 1;
}
T::op_s(&left, &right)
}
/// Applies the operator to all elements in a range.
///
/// ## Parameters
///
/// - `range`: The range of intervals. This must be `RangeBounds<usize>`.
/// - `f`: An operator.
///
/// ## Complexity
///
/// `O(log n)`
#[inline]
pub fn range_apply(&mut self, range: impl std::ops::RangeBounds<usize>, f: &T::F) {
use std::ops::Bound::{Excluded, Included, Unbounded};
let l = match range.start_bound() {
Unbounded => 0,
Included(x) => *x,
Excluded(x) => x + 1,
} + self.m;
let r = match range.end_bound() {
Unbounded => self.n,
Included(x) => x + 1,
Excluded(x) => *x,
} + self.m;
debug_assert!(
l <= r,
"invalid range: start {} must be smaller than or equal to end {}",
l - self.m,
r - self.m
);
debug_assert!(
r <= self.n + self.m,
"invalid range: range end {} must be smaller than length {}",
r - self.m,
self.n
);
for k in (1..=self.m.trailing_zeros()).rev() {
if (l >> k) << k != l {
self.push(l >> k);
}
if (r >> k) << k != r {
self.push((r - 1) >> k);
}
}
{
let (mut l, mut r) = (l, r);
while l < r {
if l & 1 == 1 {
T::apply(&mut self.data[l], f);
self.func[l] = T::op_f(&self.func[l], f);
l += 1;
}
if r & 1 == 1 {
r -= 1;
T::apply(&mut self.data[r], f);
self.func[r] = T::op_f(&self.func[r], f);
}
l >>= 1;
r >>= 1;
}
}
for k in 1..=self.m.trailing_zeros() {
if (l >> k) << k != l {
self.data[l >> k] = T::op_s(&self.data[2 * (l >> k)], &self.data[2 * (l >> k) + 1]);
}
if (r >> k) << k != r {
self.data[(r - 1) >> k] = T::op_s(
&self.data[2 * ((r - 1) >> k)],
&self.data[2 * ((r - 1) >> k) + 1],
);
}
}
}
#[inline]
fn push(&mut self, k: usize) {
let f = std::mem::replace(&mut self.func[k], T::identity_f());
T::apply(&mut self.data[2 * k], &f);
T::apply(&mut self.data[2 * k + 1], &f);
self.func[2 * k] = T::op_f(&self.func[2 * k], &f);
self.func[2 * k + 1] = T::op_f(&self.func[2 * k + 1], &f);
}
}
impl<T: MonoidAction> LazySegTree<T>
where
T::S: Clone,
{
/// Creates a new Lazy Segment Tree from a vector.
///
/// ## Parameters
///
/// - `a`: Reference of a sequence which is managed by this structure.
///
/// ## Complexity
///
/// `O(n)`
pub fn from_slice(a: &[T::S]) -> Self {
let n = a.len();
let m = n.next_power_of_two();
let mut data = vec![T::identity_s(); 2 * m];
data[m..m + n].clone_from_slice(a);
for i in (1..m).rev() {
data[i] = T::op_s(&data[2 * i], &data[2 * i + 1]);
}
Self {
n,
m,
data: data.into_boxed_slice(),
func: vec![T::identity_f(); 2 * m].into_boxed_slice(),
}
}
}