#366338 (Rust) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

• 問題: No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
• ユーザー: pianoneko
• 提出日時: 2019-08-08 22:00:25
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 145 ms / 5,000 ms
• コード長: 8,353 bytes
• コンパイル時間: 3,810 ms
• コンパイル使用メモリ: 162,176 KB
• 実行使用メモリ: 7,320 KB
• 最終ジャッジ日時: 2023-09-26 01:46:14
• 合計ジャッジ時間: 4,746 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	7 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	3 ms; 4,376 KB
testcase_09	AC	64 ms; 4,376 KB
testcase_10	AC	58 ms; 4,380 KB
testcase_11	AC	36 ms; 4,376 KB
testcase_12	AC	65 ms; 4,580 KB
testcase_13	AC	10 ms; 4,380 KB
testcase_14	AC	53 ms; 4,376 KB
testcase_15	AC	95 ms; 4,376 KB
testcase_16	AC	113 ms; 6,584 KB
testcase_17	AC	145 ms; 7,052 KB
testcase_18	AC	81 ms; 7,320 KB
testcase_19	AC	84 ms; 7,144 KB

コンパイルメッセージ

warning: unused import: `std::collections::*`
 --> Main.rs:2:5
  |
2 | use std::collections::*;
  |     ^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::io::BufRead`
 --> Main.rs:4:5
  |
4 | use std::io::BufRead;
  |     ^^^^^^^^^^^^^^^^

warning: unused imports: `Add`, `Sub`
 --> Main.rs:6:16
  |
6 | use std::ops::{Add, Sub};
  |                ^^^  ^^^

warning: function `read` is never used
  --> Main.rs:24:4
   |
24 | fn read<T: FromStr>() -> T {
   |    ^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: field `n` is never read
   --> Main.rs:219:5
    |
218 | pub struct LazySegmentTree<M: Monoid, O: OperatorMonoid<T = M::T>> {
    |            --------------- field in this struct
219 |     n: usize,
    |     ^
    |
    = note: `LazySegmentTree` has a derived impl for the trait `Debug`, but this is intentionally ignored during dead code analysis

warning: 5 warnings emitted

ソースコード

use std::cmp::*;
use std::collections::*;
use std::fmt::Debug;
use std::io::BufRead;
use std::io::{stdin, Read};
use std::ops::{Add, Sub};
use std::str::FromStr;

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

macro_rules! read {
    (($($t:tt),*)) => {
        ( $(read!($t)),* )
    };
    ([[$t:tt; $len1:expr]; $len2:expr]) => {
        (0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()
    };

    ([$t:tt; $len:expr]) => {
        (0..$len).map(|_| read!($t)).collect::<Vec<_>>()
    };

    (chars) => {
        read!(String).chars().collect::<Vec<char>>()
    };

    (usize1) => {
        read!(usize) - 1
    };

    ($t:ty) => {{
        let stdin = stdin();
        let stdin = stdin.lock();
        let token: String = stdin
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        token.parse::<$t>().unwrap()
    }};
}

macro_rules! input {
    (mut $name:ident: $t:tt, $($r:tt)*) => {
        let mut $name = read!($t);
        $(println!("{}", stringify!($r));)*
        input!($($r)*);
    };

    (mut $name:ident: $t:tt) => {
        let mut $name = read!($t);
    };

    ($name:ident: $t:tt, $($r:tt)*) => {
        let $name = read!($t);
        input!($($r)*);
    };

    ($name:ident: $t:tt) => {
        let $name = read!($t);
    };
}

trait VecExt {
    fn cumulation(&self) -> Vec<i64>;
    fn cumulation_query(&self, a: usize, b: usize) -> i64;
}

impl VecExt for Vec<i64> {
    fn cumulation(&self) -> Vec<i64> {
        let mut vec = vec![0; self.len() + 1];
        for i in 0..self.len() {
            vec[i + 1] = self[i] + vec[i];
        }
        return vec;
    }

    fn cumulation_query(&self, left: usize, right: usize) -> i64 {
        return self[right] - self[left];
    }
}

pub trait Monoid {
    type T: Copy + Clone + std::fmt::Debug + PartialOrd;
    fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T;
    fn identity() -> Self::T;
}

pub trait OperatorMonoid {
    type T;
    type U: Copy + Clone + std::fmt::Debug + PartialOrd;
    fn op1(lhs: &Self::U, rhs: &Self::U) -> Self::U;
    fn op2(lhs: &Self::T, rhs: &Self::U, len: &usize) -> Self::T;
    fn identity() -> Self::U;
}

#[derive(Clone)]
struct Sum;

impl Monoid for Sum {
    type T = i64;
    fn identity() -> Self::T {
        return 0;
    }

    fn op(a: &Self::T, b: &Self::T) -> Self::T {
        return a + b;
    }
}

#[derive(Clone)]
struct Max {}

impl Monoid for Max {
    type T = i64;

    fn identity() -> Self::T {
        return 0
    }

    fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T {
        return std::cmp::max(*lhs, *rhs);
    }
}

#[derive(Clone)]
struct OperatorMax {}

impl OperatorMonoid for OperatorMax {
    type T = i64;
    type U = Option<i64>;

    fn identity() -> Self::U {
        return None;
    }

    fn op1(_query: &Self::U, rhs: &Self::U) -> Self::U {
        return *rhs
    }

    fn op2(lhs: &Self::T, rhs: &Self::U, _: &usize) -> Self::T {
        if rhs.is_some() {
            (*rhs).unwrap()
        } else {
            *lhs
        }
    }
}

#[derive(Clone)]
struct Min {}

impl Monoid for Min {
    type T = i64;

    fn identity() -> Self::T {
        return (1 << 31) - 1 
    }

    fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T {
        return std::cmp::min(*lhs, *rhs);
    }
}

#[derive(Clone)]
struct OperatorMin {}

impl OperatorMonoid for OperatorMin {
    type T = i64;
    type U = Option<i64>;

    fn identity() -> Self::U {
        return None;
    }

    fn op1(_: &Self::U, rhs: &Self::U) -> Self::U {
        return *rhs
    }

    fn op2(lhs: &Self::T, rhs: &Self::U, _: &usize) -> Self::T {
        if rhs.is_some() {
            (*rhs).unwrap()
        } else {
            *lhs
        }
    }
}

#[derive(Debug)]
pub struct LazySegmentTree<M: Monoid, O: OperatorMonoid<T = M::T>> {
    n: usize,
    size: usize,
    data: Vec<M::T>,
    lazy: Vec<O::U>,
}

impl<M: Monoid, O: OperatorMonoid<T = M::T>> LazySegmentTree<M, O> {
    pub fn new(n: usize) -> LazySegmentTree<M, O> {
        let mut size = 1;
        while size < n {
            size *= 2;
        }

        LazySegmentTree {
            n: n,
            size: size,
            data: vec![M::identity(); size * 2],
            lazy: vec![O::identity(); size * 2],
        }
    }

    pub fn set(&mut self, k: usize, v: M::T) {
        self.data[k + self.size] = v;
    }

    pub fn build(&mut self) {
        for k in (1..self.size - 1).rev() {
            self.data[k] = M::op(&self.data[k * 2], &self.data[k * 2 + 1]);
        }
    }

    pub fn propagate(&mut self, k: usize, len: usize) {
        if self.lazy[k] != O::identity() {
            self.data[k] = O::op2(&self.data[k], &self.lazy[k], &len);
            if k < self.size {
                self.lazy[2 * k + 0] = O::op1(&self.lazy[2 * k + 0], &self.lazy[k]);
                self.lazy[2 * k + 1] = O::op1(&self.lazy[2 * k + 1], &self.lazy[k]);
            }
            self.lazy[k] = O::identity();
        }
    }

    pub fn _update(&mut self, a: usize, b: usize, x: O::U, k: usize, l: usize, r: usize) {
        self.propagate(k, r - l);
        if r <= a || b <= l {
            return;
        } else if a <= l && r <= b {
            self.lazy[k] = O::op1(&self.lazy[k], &x);
            self.propagate(k, r - l);
        } else {
            self._update(a, b, x, 2 * k + 0, l, (l + r) >> 1);
            self._update(a, b, x, 2 * k + 1, (l + r) >> 1, r);
            self.data[k] = M::op(&self.data[2 * k + 0], &self.data[2 * k + 1]);
        }
    }

    pub fn update(&mut self, a: usize, b: usize, x: O::U) {
        let sz = self.size;
        self._update(a, b, x, 1, 0, sz);
    }

    fn _query(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> M::T {
        self.propagate(k, r - l);
        if r <= a || b <= l {
            return M::identity();
        } else if a <= l && r <= b {
            return self.data[k];
        } else {
            return M::op(
                &self._query(a, b, 2 * k + 0, l, (l + r) >> 1),
                &self._query(a, b, 2 * k + 1, (l + r) >> 1, r),
            );
        }
    }

    pub fn query(&mut self, a: usize, b: usize) -> M::T {
        let sz = self.size;
        return self._query(a, b, 1, 0, sz);
    }
}

#[derive(Clone)]
struct Hoge {}

impl Monoid for Hoge {
    type T = (i64, i64);
    fn identity() -> Self::T {
        (0, 0)
    }

    fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T {
        (lhs.0 + rhs.0, lhs.1 + rhs.1)
    }
}

#[derive(Clone)]
struct OperatorHoge {}

impl OperatorMonoid for OperatorHoge {
    type T = (i64, i64);
    type U = i64;
    fn identity() -> Self::U {
        -1
    }
    fn op1(_: &Self::U, rhs: &Self::U) -> Self::U {
        *rhs
    }
    fn op2(lhs: &Self::T, rhs: &Self::U, len: &usize) -> Self::T {
        match rhs {
            1 => (*len as i64, 0),
            2 => (0, *len as i64),
            _ => *lhs,
        }
    }
}

fn main() {
    input!(n: usize, q: usize);
    let mut seg: LazySegmentTree<Hoge, OperatorHoge> = LazySegmentTree::new(n);
    let mut sum_a = 0;
    let mut sum_b = 0;
    for _ in 0..q {
        input!(x: usize, l: usize, mut r: usize);
        r += 1;
        if x == 0 {
            let cnt = seg.query(l, r);
            if cnt.0 > cnt.1 {
                sum_a += cnt.0;
            } else if cnt.0 < cnt.1 {
                sum_b += cnt.1;
            }
        } else if x == 1 {
            seg.update(l, r, 1);
        } else {
            seg.update(l, r, 2);
        }
    }

    let cnt = seg.query(0, n);

    println!("{} {}", sum_a + cnt.0, sum_b + cnt.1);
}