結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー lp_ql
提出日時 2025-09-06 15:07:12
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 4,729 bytes
コンパイル時間 21,304 ms
コンパイル使用メモリ 376,792 KB
実行使用メモリ 61,144 KB
最終ジャッジ日時 2025-09-06 15:08:47
合計ジャッジ時間 52,777 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: method `update` is never used
  --> src/main.rs:78:8
   |
67 | impl<M: Monoid> DynamicSegtree<M> {
   | --------------------------------- method in this implementation
...
78 |     fn update(&mut self, idx: usize, val: M::S) {
   |        ^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use proconio::{input, marker::Usize1};
fn main() {
    input!{
        n: usize,
        m: usize,
        mut alr: [(i64, Usize1, Usize1); n],
        q: usize,
        xyuv: [(Usize1, Usize1, Usize1, Usize1); q],
    }
    let mut seg = DynamicSegtree::<M>::new(0, m + 2);
    let mut seg2 = DynamicSegtree::<M>::new(0, m + 2);
    let mut ans: i64 = 0;
    for i in 0..n{
        seg2.set(i, alr[i].0);
        seg.set(alr[i].1, seg.prod(alr[i].1, alr[i].1 + 1) + 1);
        seg.set(alr[i].2 + 1, seg.prod(alr[i].2 + 1, alr[i].2 + 2) - 1);
        ans += alr[i].0 * (alr[i].2 - alr[i].1 + 1) as i64
    }
    for i in 0..n{
        ans -= seg.prod(0, i + 1) * alr[i].0;
    }
    let mut idx = (0..n).collect::<Vec<usize>>();
    for (x, y, u, v) in xyuv{
        ans += seg.prod(0, idx[x] + 1) * alr[x].0;
        seg.set(alr[x].1, seg.prod(alr[x].1, alr[x].1 + 1) - 1);
        seg.set(alr[x].2 + 1, seg.prod(alr[x].2 + 1, alr[x].2 + 2) + 1);
        seg2.set(idx[x], 0);
        ans += seg2.prod(alr[x].1, alr[x].2 + 1);
        ans -= alr[x].0 * (alr[x].2 - alr[x].1 + 1) as i64;
        idx[x] = y;
        (alr[x].1, alr[x].2) = (u, v);
        ans += alr[x].0 * (alr[x].2 - alr[x].1 + 1) as i64;
        ans -= seg2.prod(alr[x].1, alr[x].2 + 1);
        seg2.set(idx[x], alr[x].0);
        seg.set(alr[x].1, seg.prod(alr[x].1, alr[x].1 + 1) + 1);
        seg.set(alr[x].2 + 1, seg.prod(alr[x].2 + 1, alr[x].2 + 2) - 1);
        ans -= seg.prod(0, idx[x] + 1) * alr[x].0;
        println!("{}", ans);
    }
}

struct M;
impl Monoid for M {
    type S = i64;
    fn identity() -> Self::S {
        0
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        a + b
    }
}

trait Monoid {
    type S: Clone;
    fn identity() -> Self::S;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
}

struct DynamicSegtree<M: Monoid> {
    l: usize,         
    r: usize,         
    value: M::S,     
    left: Option<Box<DynamicSegtree<M>>>,
    right: Option<Box<DynamicSegtree<M>>>,
}

impl<M: Monoid> DynamicSegtree<M> {
    fn new(l: usize, r: usize) -> Self {
        Self {
            l,
            r,
            value: M::identity(),
            left: None,
            right: None,
        }
    }

    fn update(&mut self, idx: usize, val: M::S) {
        if idx < self.l || idx >= self.r {
            return;
        }
        if self.r - self.l == 1 {
            self.value = M::binary_operation(&self.value.clone(), &val);
            return;
        }
        let mid = (self.l + self.r) / 2;
        if idx < mid {
            if self.left.is_none() {
                self.left = Some(Box::new(DynamicSegtree::<M>::new(self.l, mid)));
            }
            self.left.as_mut().unwrap().update(idx, val.clone());
        } else {
            if self.right.is_none() {
                self.right = Some(Box::new(DynamicSegtree::<M>::new(mid, self.r)));
            }
            self.right.as_mut().unwrap().update(idx, val.clone());
        }
        let left_val = self.left.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity());
        let right_val = self.right.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity());
        self.value = M::binary_operation(&left_val, &right_val);
    }

    fn set(&mut self, idx: usize, val: M::S) {
        if idx < self.l || idx >= self.r {
            return;
        }
        if self.r - self.l == 1 {
            self.value = val;
            return;
        }
        let mid = (self.l + self.r) / 2;
        if idx < mid {
            if self.left.is_none() {
                self.left = Some(Box::new(DynamicSegtree::<M>::new(self.l, mid)));
            }
            self.left.as_mut().unwrap().set(idx, val.clone());
        } else {
            if self.right.is_none() {
                self.right = Some(Box::new(DynamicSegtree::<M>::new(mid, self.r)));
            }
            self.right.as_mut().unwrap().set(idx, val.clone());
        }
        let left_val = self.left.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity());
        let right_val = self.right.as_ref().map(|node| node.value.clone()).unwrap_or(M::identity());
        self.value = M::binary_operation(&left_val, &right_val);
    }

 
    fn prod(&self, ql: usize, qr: usize) -> M::S {
        if self.r <= ql || qr <= self.l {
            return M::identity();
        }
        if ql <= self.l && self.r <= qr {
            return self.value.clone();
        }
        let left_res = self.left.as_ref().map(|node| node.prod(ql, qr)).unwrap_or(M::identity());
        let right_res = self.right.as_ref().map(|node| node.prod(ql, qr)).unwrap_or(M::identity());
        M::binary_operation(&left_res, &right_res)
    }
}
0