結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー akakimidoriakakimidori
提出日時 2020-02-27 23:55:33
言語 Rust
(1.77.0)
結果
AC  
実行時間 509 ms / 5,000 ms
コード長 4,567 bytes
コンパイル時間 2,617 ms
コンパイル使用メモリ 178,108 KB
実行使用メモリ 14,880 KB
最終ジャッジ日時 2023-10-24 02:48:00
合計ジャッジ時間 10,534 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 2 ms
4,368 KB
testcase_03 AC 2 ms
4,368 KB
testcase_04 AC 2 ms
4,368 KB
testcase_05 AC 2 ms
4,368 KB
testcase_06 AC 1 ms
4,368 KB
testcase_07 AC 2 ms
4,368 KB
testcase_08 AC 1 ms
4,368 KB
testcase_09 AC 2 ms
4,368 KB
testcase_10 AC 2 ms
4,368 KB
testcase_11 AC 380 ms
14,616 KB
testcase_12 AC 375 ms
14,616 KB
testcase_13 AC 265 ms
14,120 KB
testcase_14 AC 373 ms
14,616 KB
testcase_15 AC 400 ms
14,880 KB
testcase_16 AC 418 ms
14,880 KB
testcase_17 AC 501 ms
14,880 KB
testcase_18 AC 509 ms
14,880 KB
testcase_19 AC 87 ms
14,352 KB
testcase_20 AC 91 ms
14,352 KB
testcase_21 AC 92 ms
14,352 KB
testcase_22 AC 93 ms
14,352 KB
testcase_23 AC 91 ms
14,352 KB
testcase_24 AC 77 ms
13,856 KB
testcase_25 AC 84 ms
13,856 KB
testcase_26 AC 81 ms
13,856 KB
testcase_27 AC 82 ms
13,856 KB
testcase_28 AC 83 ms
13,856 KB
testcase_29 AC 366 ms
14,616 KB
testcase_30 AC 391 ms
14,616 KB
testcase_31 AC 417 ms
14,880 KB
testcase_32 AC 54 ms
13,856 KB
testcase_33 AC 61 ms
14,120 KB
testcase_34 AC 64 ms
14,088 KB
testcase_35 AC 60 ms
14,120 KB
testcase_36 AC 59 ms
14,120 KB
testcase_37 AC 63 ms
14,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;
use std::io::Write;
use std::cmp::*;

const INF: u64 = 1_000_000_000 + 1;

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: u64, b: u64) -> u64 {
    assert!(a > 0 && b > 0);
    a / gcd(a, b) * b
}

struct Value {
    sum: u64,
    laz: u64,
    lcm: u64,
    max: u64,
    len: u64,
}

impl Value {
    fn new(val: u64) -> Self {
        Value {
            sum: val,
            laz: 0,
            lcm: val,
            max: val,
            len: 1,
        }
    }
    fn get_sum(&self) -> u64 {
        self.sum
    }
    fn get_max(&self) -> u64 {
        self.max
    }
    fn assign(&mut self, val: u64) {
        self.sum = val * self.len;
        self.laz = val;
        self.lcm = val;
        self.max = val;
    }
    fn fold(&self, rhs: &Self) -> Self {
        Value {
            sum: self.sum + rhs.sum,
            laz: 0,
            lcm: min(INF, lcm(self.lcm, rhs.lcm)),
            max: max(self.max, rhs.max),
            len: self.len + rhs.len,
        }
    }
    fn chgcd_break(&self, val: u64) -> bool {
        self.lcm != INF && val % self.lcm == 0
    }
    fn tag(&self) -> bool {
        self.laz > 0
    }
    fn chgcd(&mut self, val: u64) {
        assert!(self.laz > 0);
        let v = gcd(self.laz, val);
        self.assign(v);
    }
}

fn update(seg: &mut [Value], k: usize) {
    seg[k] = seg[2 * k].fold(&seg[2 * k + 1])
}

fn propagate(seg: &mut [Value], k: usize) {
    let v = seg[k].laz;
    seg[k].laz = 0;
    if v > 0 {
        seg[2 * k].assign(v);
        seg[2 * k + 1].assign(v);
    }
}

fn update_assign(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: u64) {
    if r <= x || y <= l {
        return;
    }
    if x <= l && r <= y {
        seg[k].assign(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_assign(seg, 2 * k, l, m, x, y, val);
    update_assign(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn update_chgcd(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: u64) {
    if r <= x || y <= l || seg[k].chgcd_break(val) {
        return;
    }
    if x <= l && r <= y && seg[k].tag() {
        seg[k].chgcd(val);
        return;
    }
    propagate(seg, k);
    let m = (l + r) / 2;
    update_chgcd(seg, 2 * k, l, m, x, y, val);
    update_chgcd(seg, 2 * k + 1, m, r, x, y, val);
    update(seg, k);
}

fn find_max(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> u64 {
    if r <= x || y <= l {
        0
    } else if x <= l && r <= y {
        seg[k].get_max()
    } else {
        propagate(seg, k);
        let m = (l + r) / 2;
        max(find_max(seg, 2 * k, l, m, x, y), find_max(seg, 2 * k + 1, m, r, x, y))
    }
}

fn find_sum(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> u64 {
    if r <= x || y <= l {
        0
    } else if x <= l && r <= y {
        seg[k].get_sum()
    } else {
        propagate(seg, k);
        let m = (l + r) / 2;
        find_sum(seg, 2 * k, l, m, x, y) + find_sum(seg, 2 * k + 1, m, r, x, y)
    }
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();
    let size = n.next_power_of_two();
    let mut seg: Vec<_> = (0..(2 * size)).map(|_| Value::new(1)).collect();
    for s in seg[size..].iter_mut().take(n) {
        s.assign(it.next().unwrap().parse().unwrap());
    }
    for i in (1..size).rev() {
        update(&mut seg, i);
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for _ in 0..q {
        let op: usize = it.next().unwrap().parse().unwrap();
        let l: usize = it.next().unwrap().parse().unwrap();
        let r: usize = it.next().unwrap().parse().unwrap();
        if op == 1 {
            let x: u64 = it.next().unwrap().parse().unwrap();
            update_assign(&mut seg, 1, 0, size, l - 1, r, x);
        } else if op == 2 {
            let x: u64 = it.next().unwrap().parse().unwrap();
            update_chgcd(&mut seg, 1, 0, size, l - 1, r, x);
        } else if op == 3 {
            let ans = find_max(&mut seg, 1, 0, size, l - 1, r);
            writeln!(out, "{}", ans).ok();
        } else {
            let ans = find_sum(&mut seg, 1, 0, size, l - 1, r);
            writeln!(out, "{}", ans).ok();
        }
    }
}

fn main() {
    run();
}
0