結果
| 問題 | No.3424 Shooting Game |
| コンテスト | |
| ユーザー |
 urectanc
|
| 提出日時 | 2026-01-11 16:14:29 |
| 言語 | Rust (1.92.0 + proconio + num) |
| 結果 |
AC
|
| 実行時間 | 242 ms / 2,000 ms |
| コード長 | 8,531 bytes |
| 記録 | |
| コンパイル時間 | 23,360 ms |
| コンパイル使用メモリ | 414,964 KB |
| 実行使用メモリ | 19,936 KB |
| 最終ジャッジ日時 | 2026-01-11 17:24:41 |
| 合計ジャッジ時間 | 26,545 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 11 |
ソースコード
use proconio::input;
const M: usize = 400_010;
fn main() {
input! {
n: usize, t: usize,
mut targets: [(usize, usize, usize); n],
}
targets.sort_unstable_by_key(|t| t.2);
let mut best = lazy_segtree::LazySegmentTree::<RangeUpdate>::new(M);
for &(l, r, p) in &targets {
best.apply_range(l, r + 1, Some(p));
}
let mut dp = vec![0; M];
for i in 1..M {
dp[i] = dp[i].max(dp[i - 1]);
if i >= t {
dp[i] = dp[i].max(dp[i - t] + best.get(i - t));
}
}
let ans = dp[M - 1];
println!("{ans}");
}
struct RangeUpdate;
impl lazy_segtree::Operator for RangeUpdate {
type Value = usize;
type Map = Option<usize>;
fn identity() -> Self::Value {
0
}
fn identity_map() -> Self::Map {
None
}
fn op(a: &Self::Value, b: &Self::Value) -> Self::Value {
*a + *b
}
fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value {
f.unwrap_or(*x)
}
fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map {
f.or(*g)
}
}
#[allow(unused)]
mod lazy_segtree {
pub trait Operator {
type Value: Clone;
type Map: Clone;
fn identity() -> Self::Value;
fn identity_map() -> Self::Map;
fn op(a: &Self::Value, b: &Self::Value) -> Self::Value;
fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value;
fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map;
}
pub struct LazySegmentTree<O: Operator> {
n: usize,
offset: usize,
height: usize,
value: Vec<O::Value>,
map: Vec<O::Map>,
}
impl<O: Operator> From<Vec<O::Value>> for LazySegmentTree<O> {
fn from(v: Vec<O::Value>) -> Self {
let n = v.len();
let offset = n.next_power_of_two();
let height = offset.trailing_zeros() as usize;
let mut value = vec![O::identity(); 2 * offset];
value[offset..][..n].clone_from_slice(&v);
let map = vec![O::identity_map(); offset];
let mut ret = Self {
n,
offset,
height,
value,
map,
};
for i in (1..offset).rev() {
ret.update(i);
}
ret
}
}
impl<O: Operator> LazySegmentTree<O> {
pub fn new(n: usize) -> Self {
vec![O::identity(); n].into()
}
pub fn as_slice(&mut self) -> &[O::Value] {
for i in 1..self.offset {
self.push(i);
}
&self.value[self.offset..][..self.n]
}
pub fn get(&mut self, i: usize) -> O::Value {
debug_assert!(i < self.n);
let i = i + self.offset;
for k in (1..=self.height).rev() {
self.push(i >> k);
}
self.value[i].clone()
}
pub fn set(&mut self, i: usize, x: O::Value) {
debug_assert!(i < self.n);
let i = i + self.offset;
for k in (1..=self.height).rev() {
self.push(i >> k);
}
self.value[i] = x;
for k in 1..=self.height {
self.update(i >> k);
}
}
pub fn prod(&mut self, l: usize, r: usize) -> O::Value {
debug_assert!(l <= r && r <= self.n);
let (mut l, mut r) = (l + self.offset, r + self.offset);
for k in (1..=self.height).rev() {
if ((l >> k) << k) != l {
self.push(l >> k);
}
if ((r >> k) << k) != r {
self.push(r >> k);
}
}
let mut prod_l = O::identity();
let mut prod_r = O::identity();
while l < r {
if l & 1 == 1 {
prod_l = O::op(&prod_l, &self.value[l]);
l += 1;
}
if r & 1 == 1 {
prod_r = O::op(&self.value[r - 1], &prod_r);
}
l >>= 1;
r >>= 1;
}
O::op(&prod_l, &prod_r)
}
pub fn all_prod(&self) -> O::Value {
self.value[1].clone()
}
pub fn apply(&mut self, i: usize, f: O::Map) {
debug_assert!(i < self.n);
let i = i + self.offset;
for k in (1..=self.height).rev() {
self.push(i >> k);
}
self.value[i] = O::apply(&f, &self.value[i]);
for k in 1..=self.height {
self.update(i >> k);
}
}
pub fn apply_range(&mut self, l: usize, r: usize, f: O::Map) {
debug_assert!(l <= r && r <= self.n);
let (l, r) = (l + self.offset, r + self.offset);
for k in (1..=self.height).rev() {
if ((l >> k) << k) != l {
self.push(l >> k);
}
if ((r >> k) << k) != r {
self.push(r >> k);
}
}
{
let (mut l, mut r) = (l, r);
while l < r {
if l & 1 == 1 {
self.all_apply(l, &f);
l += 1;
}
if r & 1 == 1 {
self.all_apply(r - 1, &f);
}
l >>= 1;
r >>= 1;
}
}
for k in 1..=self.height {
if ((l >> k) << k) != l {
self.update(l >> k);
}
if ((r >> k) << k) != r {
self.update(r >> k);
}
}
}
pub fn max_right(&mut self, l: usize, f: impl Fn(&O::Value) -> bool) -> usize {
debug_assert!(l <= self.n);
debug_assert!(f(&O::identity()));
let mut i = l + self.offset;
for k in (1..=self.height).rev() {
self.push(i >> k);
}
let mut prod = O::identity();
loop {
i >>= i.trailing_zeros();
let next = O::op(&prod, &self.value[i]);
if !f(&next) {
break;
}
i += 1;
prod = next;
if i & i.wrapping_neg() == i {
return self.n;
}
}
while i < self.offset {
self.push(i);
i *= 2;
let next = O::op(&prod, &self.value[i]);
if f(&next) {
i += 1;
prod = next;
}
}
i - self.offset
}
pub fn min_left(&mut self, r: usize, f: impl Fn(&O::Value) -> bool) -> usize {
debug_assert!(r <= self.n);
debug_assert!(f(&O::identity()));
let mut i = r + self.offset;
for k in (1..=self.height).rev() {
self.push((i - 1) >> k);
}
let mut prod = O::identity();
loop {
i >>= i.trailing_zeros();
if i > 1 {
i -= 1;
}
let next = O::op(&self.value[i], &prod);
if !f(&next) {
break;
}
prod = next;
if i & i.wrapping_neg() == i {
return 0;
}
}
while i < self.offset {
self.push(i);
i = 2 * i + 1;
let next = O::op(&self.value[i], &prod);
if f(&next) {
i -= 1;
prod = next;
}
}
i + 1 - self.offset
}
fn update(&mut self, i: usize) {
self.value[i] = O::op(&self.value[2 * i], &self.value[2 * i + 1]);
}
fn all_apply(&mut self, i: usize, f: &O::Map) {
self.value[i] = O::apply(f, &self.value[i]);
if i < self.offset {
self.map[i] = O::compose(f, &self.map[i]);
}
}
fn push(&mut self, i: usize) {
let f = std::mem::replace(&mut self.map[i], O::identity_map());
self.all_apply(2 * i, &f);
self.all_apply(2 * i + 1, &f);
}
}
}