結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー nebocconebocco
提出日時 2021-09-30 16:45:35
言語 Rust
(1.77.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 12,745 bytes
コンパイル時間 13,728 ms
コンパイル使用メモリ 383,408 KB
実行使用メモリ 27,452 KB
最終ジャッジ日時 2024-09-22 19:59:46
合計ジャッジ時間 30,550 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 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 2 ms
5,376 KB
testcase_11 AC 548 ms
21,712 KB
testcase_12 AC 532 ms
22,032 KB
testcase_13 AC 387 ms
21,248 KB
testcase_14 AC 533 ms
22,540 KB
testcase_15 AC 562 ms
22,656 KB
testcase_16 AC 600 ms
22,720 KB
testcase_17 AC 651 ms
23,132 KB
testcase_18 AC 653 ms
23,004 KB
testcase_19 AC 242 ms
22,188 KB
testcase_20 AC 263 ms
22,440 KB
testcase_21 AC 256 ms
22,140 KB
testcase_22 AC 261 ms
22,168 KB
testcase_23 AC 269 ms
22,188 KB
testcase_24 AC 227 ms
21,696 KB
testcase_25 AC 230 ms
22,048 KB
testcase_26 AC 232 ms
21,648 KB
testcase_27 AC 225 ms
21,792 KB
testcase_28 AC 236 ms
21,696 KB
testcase_29 AC 523 ms
22,708 KB
testcase_30 AC 555 ms
22,644 KB
testcase_31 AC 593 ms
22,916 KB
testcase_32 TLE -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
	let mut io = IO::new();
    input!{ from io,
		n: usize, q: usize,
        l: [i64; n],
    }
	let mut seg = SegmentTreeBeats::<RangeUpdateChgcdMaxSum>::from(
        &l.into_iter().map(Rucms::new).collect()
    );
	for _ in 0..q {
		match io.scan::<i64>() {
			1 => {
				let (l, r, e) = io.scan::<(Usize1, usize, i64)>();
				seg.update(l..r, Op::Update(e));
			}
			2 => {
				let (l, r, e) = io.scan::<(Usize1, usize, i64)>();
				seg.update(l..r, Op::Gcd(e));
			}
            3 => {
				let (l, r) = io.scan::<(Usize1, usize)>();
				io.println(seg.fold(l..r).max)
			}
            4 => {
				let (l, r) = io.scan::<(Usize1, usize)>();
				io.println(seg.fold(l..r).sum)
			}
			_ => unreachable!()

		}
	}
}

pub fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        a %= b;
        std::mem::swap(&mut a, &mut b);
    }
    a
}

pub fn lcm(a: i64, b: i64) -> i64 {
    if a == 0 && b == 0 {
        0
    } else {
        (a / gcd(a, b)).saturating_mul(b)
    }
}

#[derive(Clone, PartialEq)]
struct Rucms {
    max: i64,
    lcm: i64,
    sum: i64,
    size: i64,
    fail: bool
}

impl Rucms {
    fn new(val: i64) -> Self {
        Self {
            max: val,
            lcm: val,
            sum: val,
            size: 1,
            fail: false
        }
    }
}

impl Beats for Rucms {
    fn is_failed(&self) -> bool { self.fail }
}

#[derive(Clone, PartialEq)]
enum Op {
    Gcd(i64),
    Update(i64),
    None
}

struct RangeUpdateChgcdMaxSum;
impl Operation for RangeUpdateChgcdMaxSum {
    type Val = Rucms;
    type Eff = Op;
    const ZERO_VAL: Self::Val = Rucms{
        max: 0, lcm: 1, sum: 0, size: 0, fail: false
    };
    const ZERO_EFF: Self::Eff = Op::None;
    fn op_val(left: &Self::Val, right: &Self::Val) -> Self::Val {
        Self::Val {
            max: left.max.max(right.max),
            lcm: lcm(left.lcm, right.lcm),
            sum: left.sum + right.sum,
            size: left.size + right.size,
            fail: left.fail | right.fail
        }
    }
    fn op_eff(left: &Self::Eff, right: &Self::Eff) -> Self::Eff {
        match (left, right) {
            (left, Op::None) => left.clone(),
            (Op::None, right) => right.clone(),
            (_, Op::Update(_)) => right.clone(),
            (Op::Gcd(a), Op::Gcd(b)) => Op::Gcd(gcd(*a, *b)),
            (Op::Update(a), Op::Gcd(b)) => Op::Update(gcd(*a, *b))
        }
    }
    fn effect(val: &Self::Val, eff: &Self::Eff) -> Self::Val {
        let mut res = val.clone();
        match *eff {
            Op::Gcd(g) => {
                if val.size == 1 {
                    res = Rucms::new(gcd(g, val.max));
                } else if g % val.lcm != 0 {
                    res.fail = true;
                }
            }
            Op::Update(u) => {
                res.max = u;
                res.lcm = u;
                res.sum = u * res.size;
            }
            Op::None => ()
        };
        res
    }
}

// ------------ Segment Tree Beats start ------------

pub trait Operation {
    type Val: Clone + PartialEq + Beats;
    type Eff: Clone + PartialEq;
    const ZERO_VAL: Self::Val;
    const ZERO_EFF: Self::Eff;
    fn op_val(left: &Self::Val, right: &Self::Val) -> Self::Val;
    fn op_eff(left: &Self::Eff, right: &Self::Eff) -> Self::Eff;
    fn effect(val: &Self::Val, eff: &Self::Eff) -> Self::Val;
    fn multiply(eff: &Self::Eff, _times: u32) -> Self::Eff { eff.clone() }
}

pub trait Beats {
    fn is_failed(&self) -> bool;
}

#[derive(Clone)]
struct Node<T, E> {
    val: T,
    lazy: E,
}

impl<T, E> Node<T, E> {
    fn new(val: T, lazy: E) -> Self {
        Self { val, lazy }
    }
}

pub struct SegmentTreeBeats<O: Operation> {
    node: Box<[Node<O::Val, O::Eff>]>,
    size: usize,
    dep: u32,
}

impl<O: Operation> SegmentTreeBeats<O> {
    pub fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        let dep = size.trailing_zeros() + 1;
        let node = vec![Node::new(O::ZERO_VAL, O::ZERO_EFF); size << 1]
            .into_boxed_slice();
        Self { node, size, dep }
    }

    #[inline]
    fn degree(&self, i: usize) -> u32 {
        1 << (i.leading_zeros() + self.dep - 64)
    }

    fn effect(&mut self, i: usize, e: &O::Eff) {
        self.node[i].val = O::effect(&self.node[i].val, &O::multiply(e, self.degree(i)));
        if i <= self.size {
            self.node[i].lazy = O::op_eff(&self.node[i].lazy, e);
            if self.node[i].val.is_failed() {
                self.push(i);
                self.node[i].val = O::op_val(&self.node[i << 1].val, &self.node[(i << 1) + 1].val);
            }
        }
    }

    fn push(&mut self, i: usize) {
        let e = std::mem::replace(&mut self.node[i].lazy, O::ZERO_EFF);
        if e != O::ZERO_EFF && i <= self.size {
            self.effect(i << 1, &e);
            self.effect((i << 1) + 1, &e);
        }
    }

    fn infuse(&mut self, mut i: usize) {
        i >>= i.trailing_zeros();
        while i > 1 {
            i >>= 1;
            self.node[i].val = O::op_val(&self.node[i << 1].val, &self.node[(i << 1) + 1].val);
        }
    }

    fn infiltrate(&mut self, i: usize) {
        if i < self.size << 1 {
            let d = i.trailing_zeros();
            for j in (d..self.dep).rev() {
                self.push(i >> j);
            }
        }
    }

    pub fn update<Rng: std::ops::RangeBounds<usize>>(&mut self, rng: Rng, e: O::Eff) {
        let rng = bounds_within(rng, self.size);
        let mut l = rng.start + self.size;
        let mut r = rng.end + self.size;
        self.infiltrate(l);
        self.infiltrate(r);
        while l < r {
            if l & 1 == 1 {
                self.effect(l, &e);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                self.effect(r, &e);
            }
            l >>= 1;
            r >>= 1;
        }
        self.infuse(rng.start + self.size);
        self.infuse(rng.end + self.size);
    }

    pub fn fold<Rng: std::ops::RangeBounds<usize>>(&mut self, rng: Rng) -> O::Val {
        let rng = bounds_within(rng, self.size);
        let mut l = rng.start + self.size;
        let mut r = rng.end + self.size;
        self.infiltrate(l);
        self.infiltrate(r);
        let mut lx = O::ZERO_VAL;
        let mut rx = O::ZERO_VAL;
        while l < r {
            if l & 1 == 1 {
                lx = O::op_val(&lx, &self.node[l].val);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                rx = O::op_val(&self.node[r].val, &rx);
            }
            l >>= 1;
            r >>= 1;
        }
        O::op_val(&lx, &rx)
    }
}

impl<O: Operation> From<&Vec<O::Val>> for SegmentTreeBeats<O> {
    fn from(arr: &Vec<O::Val>) -> Self {
        let size = arr.len().next_power_of_two();
        let dep = size.trailing_zeros() + 1;
        let mut node = vec![Node::new(O::ZERO_VAL, O::ZERO_EFF); size << 1];
        for i in 0..arr.len() {
            node[i + size].val = arr[i].clone();
        }
        for i in (1..size).rev() {
            node[i].val = O::op_val(&node[i << 1].val, &node[(i << 1) + 1].val);
        }
        Self { node: node.into_boxed_slice(), size, dep }
    }
}

// ------------ Segment Tree Beats end ------------


pub fn bounds_within<R>(r: R, len: usize) -> std::ops::Range<usize>
    where R: std::ops::RangeBounds<usize>
{
    use std::ops::Bound;
    let end = match r.end_bound() {
        Bound::Included(&e) => e + 1,
        Bound::Excluded(&e) => e,
        Bound::Unbounded => len,
    }
    .min(len);
    let start = match r.start_bound() {
        Bound::Included(&s) => s,
        Bound::Excluded(&s) => s + 1,
        Bound::Unbounded => 0,
    }
    .min(end);
    start..end
}

// ------------ io module start ------------
use std::io::{stdout, BufWriter, Read, StdoutLock, Write};

pub struct IO {
	iter: std::str::SplitAsciiWhitespace<'static>,
	buf: BufWriter<StdoutLock<'static>>,
}

impl IO {
	pub fn new() -> Self {
		let mut input = String::new();
		std::io::stdin().read_to_string(&mut input).unwrap();
		let input = Box::leak(input.into_boxed_str());
		let out = Box::new(stdout());
		IO {
			iter: input.split_ascii_whitespace(),
			buf: BufWriter::new(Box::leak(out).lock()),
		}
	}
	fn scan_str(&mut self) -> &'static str {
		self.iter.next().unwrap()
	}
	pub fn scan<T: Scan>(&mut self) -> <T as Scan>::Output {
		<T as Scan>::scan(self)
	}
	pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<<T as Scan>::Output> {
		(0..n).map(|_| self.scan::<T>()).collect()
	}
	pub fn print<T: Print>(&mut self, x: T) {
		<T as Print>::print(self, x);
	}
	pub fn println<T: Print>(&mut self, x: T) {
		self.print(x);
		self.print("\n");
	}
	pub fn iterln<T: Print, I: Iterator<Item = T>>(&mut self, mut iter: I, delim: &str) {
		if let Some(v) = iter.next() {
			self.print(v);
			for v in iter {
				self.print(delim);
				self.print(v);
			}
		}
		self.print("\n");
	}
	pub fn flush(&mut self) {
		self.buf.flush().unwrap();
	}
}

impl Default for IO {
	fn default() -> Self {
		Self::new()
	}
}

pub trait Scan {
	type Output;
	fn scan(io: &mut IO) -> Self::Output;
}

macro_rules! impl_scan {
	($($t:tt),*) => {
		$(
			impl Scan for $t {
				type Output = Self;
				fn scan(s: &mut IO) -> Self::Output {
					s.scan_str().parse().unwrap()
				}
			}
		)*
	};
}

impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64);

impl Scan for char {
	type Output = char;
	fn scan(s: &mut IO) -> Self::Output {
		s.scan_str().chars().next().unwrap()
	}
}

pub enum Bytes {}
impl Scan for Bytes {
	type Output = &'static [u8];
	fn scan(s: &mut IO) -> Self::Output {
		s.scan_str().as_bytes()
	}
}

pub enum Chars {}
impl Scan for Chars {
	type Output = Vec<char>;
	fn scan(s: &mut IO) -> Self::Output {
		s.scan_str().chars().collect()
	}
}

pub enum Usize1 {}
impl Scan for Usize1 {
	type Output = usize;
	fn scan(s: &mut IO) -> Self::Output {
		s.scan::<usize>().wrapping_sub(1)
	}
}

impl<T: Scan, U: Scan> Scan for (T, U) {
	type Output = (T::Output, U::Output);
	fn scan(s: &mut IO) -> Self::Output {
		(T::scan(s), U::scan(s))
	}
}

impl<T: Scan, U: Scan, V: Scan> Scan for (T, U, V) {
	type Output = (T::Output, U::Output, V::Output);
	fn scan(s: &mut IO) -> Self::Output {
		(T::scan(s), U::scan(s), V::scan(s))
	}
}

impl<T: Scan, U: Scan, V: Scan, W: Scan> Scan for (T, U, V, W) {
	type Output = (T::Output, U::Output, V::Output, W::Output);
	fn scan(s: &mut IO) -> Self::Output {
		(T::scan(s), U::scan(s), V::scan(s), W::scan(s))
	}
}

pub trait Print {
	fn print(w: &mut IO, x: Self);
}

macro_rules! impl_print_int {
	($($t:ty),*) => {
		$(
			impl Print for $t {
				fn print(w: &mut IO, x: Self) {
					w.buf.write_all(x.to_string().as_bytes()).unwrap();
				}
			}
		)*
	};
}

impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64);

impl Print for u8 {
	fn print(w: &mut IO, x: Self) {
		w.buf.write_all(&[x]).unwrap();
	}
}

impl Print for &[u8] {
	fn print(w: &mut IO, x: Self) {
		w.buf.write_all(x).unwrap();
	}
}

impl Print for &str {
	fn print(w: &mut IO, x: Self) {
		w.print(x.as_bytes());
	}
}

impl Print for String {
	fn print(w: &mut IO, x: Self) {
		w.print(x.as_bytes());
	}
}

impl<T: Print, U: Print> Print for (T, U) {
	fn print(w: &mut IO, (x, y): Self) {
		w.print(x);
		w.print(" ");
		w.print(y);
	}
}

impl<T: Print, U: Print, V: Print> Print for (T, U, V) {
	fn print(w: &mut IO, (x, y, z): Self) {
		w.print(x);
		w.print(" ");
		w.print(y);
		w.print(" ");
		w.print(z);
	}
}

mod neboccoio_macro {
	#[macro_export]
	macro_rules! input {
		(@start $io:tt @read @rest) => {};

		(@start $io:tt @read @rest, $($rest: tt)*) => {
			input!(@start $io @read @rest $($rest)*)
		};

		(@start $io:tt @read @rest mut $($rest:tt)*) => {
			input!(@start $io @read @mut [mut] @rest $($rest)*)
		};

		(@start $io:tt @read @rest $($rest:tt)*) => {
			input!(@start $io @read @mut [] @rest $($rest)*)
		};

		(@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [[$kind:tt; $len1:expr]; $len2:expr] $($rest:tt)*) => {
			let $($mut)* $var = (0..$len2).map(|_| $io.scan_vec::<$kind>($len1)).collect::<Vec<Vec<$kind>>>();
			input!(@start $io @read @rest $($rest)*)
		};

		(@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => {
			let $($mut)* $var = $io.scan_vec::<$kind>($len);
			input!(@start $io @read @rest $($rest)*)
		};

		(@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => {
			let $($mut)* $var = $io.scan::<$kind>();
			input!(@start $io @read @rest $($rest)*)
		};

		(from $io:tt $($rest:tt)*) => {
			input!(@start $io @read @rest $($rest)*)
		};
	}
}

// ------------ io module end ------------
0