#1126123 (Rust) No.3302 Sense Battle

• 問題: No.3302 Sense Battle
• ユーザー: KA37RI
• 提出日時: 2025-10-05 16:12:23
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 6,331 bytes
• コンパイル時間: 12,035 ms
• コンパイル使用メモリ: 401,844 KB
• 実行使用メモリ: 10,148 KB
• 最終ジャッジ日時: 2025-10-05 16:12:40
• 合計ジャッジ時間: 17,117 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 1 TLE * 1 -- * 16

コンパイルメッセージ

warning: methods `get_slice`, `max_right`, and `min_left` are never used
   --> src/main.rs:119:12
    |
104 |   impl<M: Monoid> Segtree<M> {
    |   -------------------------- methods in this implementation
...
119 |     pub fn get_slice(&self) -> &[M::S] {
    |            ^^^^^^^^^
...
170 |     pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
    |            ^^^^^^^^^
...
208 |     pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
    |            ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

ソースコード

use std::u64;

use proconio::input;
use segment_tree::{Max, Segtree};

fn solve() -> u64 {
  input! {
    n: usize,
    ab: [(u64, u64); n],
  }
  let mut table = Segtree::<Max<u64>>::new(n + 1);
  table.set(0, 0);
  for &(ai, bi) in ab.iter() {
    let mut ntable = Segtree::<Max<u64>>::new(n + 1);
    for i in 0..n {
      ntable.set(i.saturating_sub(1), table.get(i) + bi);
    }
    for i in 0..=n {
      let mx0 = table.prod(..=i);
      let mx1 = ntable.get(i);
      ntable.set(i, mx1.max(mx0 + ai * i as u64));
    }
    table = ntable;
  }
  table.get(0)
}

fn main() {
  let ans = solve();
  println!("{}", ans);
}

mod segment_tree {
  use std::{cmp, convert::Infallible, marker::PhantomData, ops::{Bound, RangeBounds}};

  // from https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/internal_bit.rs
  pub(crate) fn ceil_pow2(n: u32) -> u32 {
    32 - n.saturating_sub(1).leading_zeros()
  }

  // from https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/internal_type_traits.rs
  pub trait BoundedBelow {
    fn min_value() -> Self;
  }

  impl BoundedBelow for u64 {
  #[inline]
    fn min_value() -> Self {
      Self::MIN
    }
  }

  // from https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/segtree.rs
  pub trait Monoid {
    type S: Clone;
    fn identity() -> Self::S;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
  }

  pub struct Max<S>(Infallible, PhantomData<fn() -> S>);
  impl<S> Monoid for Max<S>
  where
    S: Copy + Ord + BoundedBelow,
  {
    type S = S;
    fn identity() -> Self::S {
      S::min_value()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
      cmp::max(*a, *b)
    }
  }

  impl<M: Monoid> Default for Segtree<M> {
    fn default() -> Self {
      Segtree::new(0)
    }
  }
  impl<M: Monoid> Segtree<M> {
    pub fn new(n: usize) -> Segtree<M> {
      vec![M::identity(); n].into()
    }
  }
  impl<M: Monoid> From<Vec<M::S>> for Segtree<M> {
    fn from(v: Vec<M::S>) -> Self {
      let n = v.len();
      let log = ceil_pow2(n as u32) as usize;
      let size = 1 << log;
      let mut d = vec![M::identity(); 2 * size];
      d[size..][..n].clone_from_slice(&v);
      let mut ret = Segtree { n, size, log, d };
      for i in (1..size).rev() {
        ret.update(i);
      }
      ret
    }
  }
  impl<M: Monoid> FromIterator<M::S> for Segtree<M> {
    fn from_iter<T: IntoIterator<Item = M::S>>(iter: T) -> Self {
      let v = iter.into_iter().collect::<Vec<_>>();
      v.into()
    }
  }
  impl<M: Monoid> Segtree<M> {
    pub fn set(&mut self, mut p: usize, x: M::S) {
      assert!(p < self.n);
      p += self.size;
      self.d[p] = x;
      for i in 1..=self.log {
        self.update(p >> i);
      }
    }

    pub fn get(&self, p: usize) -> M::S {
      assert!(p < self.n);
      self.d[p + self.size].clone()
    }

    pub fn get_slice(&self) -> &[M::S] {
      &self.d[self.size..][..self.n]
    }

    pub fn prod<R>(&self, range: R) -> M::S
    where
      R: RangeBounds<usize>,
    {
      // Trivial optimization
      if range.start_bound() == Bound::Unbounded && range.end_bound() == Bound::Unbounded {
        return self.all_prod();
      }

      let mut r = match range.end_bound() {
        Bound::Included(r) => r + 1,
        Bound::Excluded(r) => *r,
        Bound::Unbounded => self.n,
      };
      let mut l = match range.start_bound() {
        Bound::Included(l) => *l,
        Bound::Excluded(l) => l + 1,
        // TODO: There are another way of optimizing [0..r)
        Bound::Unbounded => 0,
      };

      assert!(l <= r && r <= self.n);
      let mut sml = M::identity();
      let mut smr = M::identity();
      l += self.size;
      r += self.size;

      while l < r {
        if l & 1 != 0 {
          sml = M::binary_operation(&sml, &self.d[l]);
          l += 1;
        }
        if r & 1 != 0 {
          r -= 1;
          smr = M::binary_operation(&self.d[r], &smr);
        }
        l >>= 1;
        r >>= 1;
      }

      M::binary_operation(&sml, &smr)
    }

    pub fn all_prod(&self) -> M::S {
      self.d[1].clone()
    }

    pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
    where
      F: Fn(&M::S) -> bool,
    {
      assert!(l <= self.n);
      assert!(f(&M::identity()));
      if l == self.n {
        return self.n;
      }
      l += self.size;
      let mut sm = M::identity();
      while {
        // do
        while l % 2 == 0 {
          l >>= 1;
        }
        if !f(&M::binary_operation(&sm, &self.d[l])) {
          while l < self.size {
            l *= 2;
            let res = M::binary_operation(&sm, &self.d[l]);
            if f(&res) {
              sm = res;
              l += 1;
            }
          }
          return l - self.size;
        }
        sm = M::binary_operation(&sm, &self.d[l]);
        l += 1;
        // while
        {
          let l = l as isize;
          (l & -l) != l
        }
      } {}
      self.n
    }

    pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
    where
      F: Fn(&M::S) -> bool,
    {
      assert!(r <= self.n);
      assert!(f(&M::identity()));
      if r == 0 {
        return 0;
      }
      r += self.size;
      let mut sm = M::identity();
      while {
        // do
        r -= 1;
        while r > 1 && r % 2 == 1 {
          r >>= 1;
        }
        if !f(&M::binary_operation(&self.d[r], &sm)) {
          while r < self.size {
            r = 2 * r + 1;
            let res = M::binary_operation(&self.d[r], &sm);
            if f(&res) {
              sm = res;
              r -= 1;
            }
          }
          return r + 1 - self.size;
        }
        sm = M::binary_operation(&self.d[r], &sm);
        // while
        {
          let r = r as isize;
          (r & -r) != r
        }
      } {}
      0
    }

    fn update(&mut self, k: usize) {
      self.d[k] = M::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);
    }
  }

  // Maybe we can use this someday
  // ```
  // for i in 0..=self.log {
  //   for j in 0..1 << i {
  //     print!("{}\t", self.d[(1 << i) + j]);
  //   }
  //   println!();
  // }
  // ```

  #[derive(Clone)]
  pub struct Segtree<M>
  where
    M: Monoid,
  {
    // variable name is _n in original library
    n: usize,
    size: usize,
    log: usize,
    d: Vec<M::S>,
  }

}