結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー norioc
提出日時 2025-09-07 03:00:51
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 385 ms / 2,500 ms
コード長 3,462 bytes
コンパイル時間 13,604 ms
コンパイル使用メモリ 397,304 KB
実行使用メモリ 25,728 KB
最終ジャッジ日時 2025-09-07 03:01:18
合計ジャッジ時間 25,783 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `p`
   --> src/main.rs:110:11
    |
110 |     for &(p, a, l, r) in &iwis {
    |           ^ help: if this is intentional, prefix it with an underscore: `_p`
    |
    = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

use std::io::{self, Read};

struct FenwickTree {
    n: usize,
    data: Vec<i64>,
}

impl FenwickTree {
    fn new(n: usize) -> Self {
        let n2 = n + 10;
        Self {
            n: n2,
            data: vec![0; n2 + 1],
        }
    }

    fn add(&mut self, mut p: usize, x: i64) {
        debug_assert!(p < self.n);
        p += 1;
        while p < self.data.len() {
            self.data[p] += x;
            p += p & (!p + 1); // p += p & -p
        }
    }

    fn sum(&self, mut p: usize) -> i64 {
        debug_assert!(p < self.n);
        p += 1;
        let mut s = 0;
        while p > 0 {
            s += self.data[p];
            p &= p - 1; // p -= p & -p
        }
        s
    }

    fn rangesum(&self, l: usize, r: usize) -> i64 {
        debug_assert!(l <= r && r < self.n);
        let mut s = self.sum(r);
        if l > 0 {
            s -= self.sum(l - 1);
        }
        s
    }
}

struct RAQ {
    a: FenwickTree,
    b: FenwickTree,
    n: usize,
}

impl RAQ {
    fn new(n: usize) -> Self {
        Self {
            a: FenwickTree::new(n + 10),
            b: FenwickTree::new(n + 10),
            n,
        }
    }

    fn add(&mut self, mut l: usize, mut r: usize, x: i64) {
        debug_assert!(l <= r && r < self.n);
        l += 1;
        r += 1;
        self.a.add(l, -x * (l as i64 - 1));
        self.b.add(l, x);
        self.a.add(r + 1, x * r as i64);
        self.b.add(r + 1, -x);
    }

    fn sum(&self, mut l: usize, mut r: usize) -> i64 {
        debug_assert!(l <= r && r < self.n);
        l += 1;
        r += 1;
        let res = self.a.sum(r) + self.b.sum(r) * r as i64
            - (self.a.sum(l - 1) + self.b.sum(l - 1) * (l as i64 - 1));
        res
    }

    fn get(&self, p: usize) -> i64 {
        self.sum(p, p)
    }
}

fn main() {
    // 入力全読み
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut iter = input.split_whitespace().map(|x| x.parse::<i64>().unwrap());

    let n = iter.next().unwrap() as usize;
    let m = iter.next().unwrap() as usize;

    let mut ft = FenwickTree::new(m);
    let mut raq = RAQ::new(m);

    let mut iwis: Vec<(usize, i64, usize, usize)> = Vec::new();

    for i in 0..n {
        let a = iter.next().unwrap();
        let l = iter.next().unwrap() as usize - 1;
        let r = iter.next().unwrap() as usize - 1;
        iwis.push((i, a, l, r));
        ft.add(i, a);
        raq.add(l, r, 1);
    }

    let mut tot: i64 = 0;
    for &(p, a, l, r) in &iwis {
        tot += a * (r as i64 - l as i64 + 1) - ft.rangesum(l, r);
    }

    let q = iter.next().unwrap() as usize;
    let mut output = String::new();

    for _ in 0..q {
        let x = iter.next().unwrap() as usize - 1;
        let y = iter.next().unwrap() as usize - 1;
        let u = iter.next().unwrap() as usize - 1;
        let v = iter.next().unwrap() as usize - 1;

        let mut ntot = tot;

        // 人 X を削除
        let (p, a, l, r) = iwis[x];
        ntot -= a * (r as i64 - l as i64 + 1) - ft.rangesum(l, r);
        raq.add(l, r, -1);
        ntot += raq.get(p) * a;
        ft.add(p, -a);

        // 人 X を追加
        ft.add(y, a);
        iwis[x] = (y, a, u, v);
        ntot += a * (v as i64 - u as i64 + 1) - ft.rangesum(u, v);
        ntot -= raq.get(y) * a;
        raq.add(u, v, 1);

        output.push_str(&format!("{}\n", ntot));
        tot = ntot;
    }

    print!("{}", output);
}
0