結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー akakimidoriakakimidori
提出日時 2020-02-27 23:50:14
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 4,547 bytes
コンパイル時間 18,527 ms
コンパイル使用メモリ 391,544 KB
実行使用メモリ 15,116 KB
最終ジャッジ日時 2024-10-13 16:05:01
合計ジャッジ時間 20,860 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 89 ms
14,336 KB
testcase_20 AC 91 ms
14,348 KB
testcase_21 AC 77 ms
14,336 KB
testcase_22 AC 76 ms
14,336 KB
testcase_23 AC 74 ms
14,336 KB
testcase_24 AC 64 ms
13,824 KB
testcase_25 AC 77 ms
13,872 KB
testcase_26 AC 75 ms
13,876 KB
testcase_27 AC 78 ms
13,824 KB
testcase_28 AC 68 ms
13,952 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 55 ms
13,952 KB
testcase_33 AC 59 ms
14,080 KB
testcase_34 AC 65 ms
14,156 KB
testcase_35 AC 50 ms
13,952 KB
testcase_36 AC 48 ms
14,072 KB
testcase_37 AC 48 ms
14,080 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.laz = val;
        self.sum = val * self.len;
        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 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