結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー akakimidoriakakimidori
提出日時 2020-09-21 18:22:17
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 321 ms / 5,000 ms
コード長 5,822 bytes
コンパイル時間 13,812 ms
コンパイル使用メモリ 383,364 KB
実行使用メモリ 10,212 KB
最終ジャッジ日時 2024-09-22 19:47:01
合計ジャッジ時間 20,247 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 250 ms
10,112 KB
testcase_12 AC 245 ms
10,052 KB
testcase_13 AC 173 ms
10,028 KB
testcase_14 AC 238 ms
10,112 KB
testcase_15 AC 259 ms
10,084 KB
testcase_16 AC 274 ms
10,052 KB
testcase_17 AC 321 ms
10,112 KB
testcase_18 AC 305 ms
10,128 KB
testcase_19 AC 95 ms
10,132 KB
testcase_20 AC 97 ms
10,112 KB
testcase_21 AC 97 ms
10,060 KB
testcase_22 AC 94 ms
10,008 KB
testcase_23 AC 98 ms
10,112 KB
testcase_24 AC 84 ms
10,080 KB
testcase_25 AC 85 ms
10,212 KB
testcase_26 AC 84 ms
10,112 KB
testcase_27 AC 85 ms
10,072 KB
testcase_28 AC 88 ms
10,192 KB
testcase_29 AC 230 ms
10,152 KB
testcase_30 AC 255 ms
10,108 KB
testcase_31 AC 269 ms
10,016 KB
testcase_32 AC 67 ms
9,912 KB
testcase_33 AC 65 ms
10,100 KB
testcase_34 AC 69 ms
10,052 KB
testcase_35 AC 64 ms
10,060 KB
testcase_36 AC 65 ms
10,056 KB
testcase_37 AC 66 ms
10,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

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

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}

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

const INF: u64 = 1_000_000_000 + 1;

fn lcm(a: u64, b: u64) -> u64 {
    if a >= INF || b >= INF {
        return INF;
    }
    let g = gcd(a, b);
    std::cmp::min(INF, a * b / g)
}

struct Node {
    sum: u64,
    lcm: u64,
    max: u64,
    len: u64,
}

impl Node {
    fn new(v: u64) -> Self {
        assert!(1 <= v && v <= 1_000_000_000);
        Node {
            sum: v,
            lcm: v,
            max: v,
            len: 1,
        }
    }
    fn merge(&self, rhs: &Self) -> Self {
        Node {
            sum: self.sum + rhs.sum,
            lcm: lcm(self.lcm, rhs.lcm),
            max: max(self.max, rhs.max),
            len: self.len + rhs.len,
        }
    }
    fn set(&mut self, v: u64) {
        self.sum = v * self.len;
        self.lcm = v;
        self.max = v;
    }
    fn chgcd_break(&self, v: u64) -> bool {
        self.lcm != INF && v % self.lcm == 0
    }
    fn chgcd_tag(&self) -> bool {
        self.sum == self.max * self.len
    }
    fn chgcd(&mut self, v: u64) {
        let v = gcd(self.max, v);
        self.set(v);
    }
    fn only(&self) -> Option<u64> {
        if self.sum == self.max * self.len {
            Some(self.max)
        } else {
            None
        }
    }
}

fn propagate(k: usize, node: &mut [Node]) {
    node[k].only().map(|v| {
        for p in node[(2 * k)..].iter_mut().take(2) {
            p.set(v);
        }
    });
}

fn update_set(k: usize, l: usize, r: usize, x: usize, y: usize, v: u64, node: &mut [Node]) {
    if r <= x || y <= l {
        return;
    }
    if x <= l && r <= y {
        node[k].set(v);
        return;
    }
    propagate(k, node);
    let mid = (l + r) / 2;
    update_set(2 * k, l, mid, x, y, v, node);
    update_set(2 * k + 1, mid, r, x, y, v, node);
    node[k] = node[2 * k].merge(&node[2 * k + 1]);
}

fn update_gcd(k: usize, l: usize, r: usize, x: usize, y: usize, v: u64, node: &mut [Node]) {
    if r <= x || y <= l || node[k].chgcd_break(v) {
        return;
    }
    if x <= l && r <= y && node[k].chgcd_tag() {
        node[k].chgcd(v);
        return;
    }
    propagate(k, node);
    let mid = (l + r) / 2;
    update_gcd(2 * k, l, mid, x, y, v, node);
    update_gcd(2 * k + 1, mid, r, x, y, v, node);
    node[k] = node[2 * k].merge(&node[2 * k + 1]);
}

fn find_max(k: usize, l: usize, r: usize, x: usize, y: usize, node: &mut [Node]) -> u64 {
    if r <= x || y <= l {
        return 0;
    }
    if x <= l && r <= y {
        return node[k].max;
    }
    propagate(k, node);
    let mid = (l + r) / 2;
    let a = find_max(2 * k, l, mid, x, y, node);
    let b = find_max(2 * k + 1, mid, r, x, y, node);
    max(a, b)
}

fn find_sum(k: usize, l: usize, r: usize, x: usize, y: usize, node: &mut [Node]) -> u64 {
    if r <= x || y <= l {
        return 0;
    }
    if x <= l && r <= y {
        return node[k].sum;
    }
    propagate(k, node);
    let mid = (l + r) / 2;
    let a = find_sum(2 * k, l, mid, x, y, node);
    let b = find_sum(2 * k + 1, mid, r, x, y, node);
    a + b
}

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    let n: usize = sc.next(b' ');
    let q: usize = sc.next(b'\n');
    let size = n.next_power_of_two();
    let mut node = (0..(2 * size)).map(|_| Node::new(1)).collect::<Vec<_>>();
    for (i, p) in node[size..].iter_mut().take(n).enumerate() {
        let d = if i == n - 1 {b'\n'} else {b' '};
        p.set(sc.next(d));
    }
    for i in (1..size).rev() {
        node[i] = node[2 * i].merge(&node[2 * i + 1]);
    }
    for _ in 0..q {
        let op: u8 = sc.next(b' ');
        let (l, r, x) = if op <= 2 {
            let l: usize = sc.next(b' ');
            let r: usize = sc.next(b' ');
            let x: u64 = sc.next(b'\n');
            (l - 1, r, x)
        } else {
            let l: usize = sc.next(b' ');
            let r: usize = sc.next(b'\n');
            (l - 1, r, 0)
        };
        if op == 1 {
            update_set(1, 0, size, l, r, x, &mut node);
        } else if op == 2 {
            update_gcd(1, 0, size, l, r, x, &mut node);
        } else if op == 3 {
            let ans = find_max(1, 0, size, l, r, &mut node);
            writeln!(out, "{}", ans).ok();
        } else {
            let ans = find_sum(1, 0, size, l, r, &mut node);
            writeln!(out, "{}", ans).ok();
        }
    }
}
0