結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | pianoneko |
提出日時 | 2019-08-08 22:00:25 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 117 ms / 5,000 ms |
コード長 | 8,353 bytes |
コンパイル時間 | 13,322 ms |
コンパイル使用メモリ | 380,628 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-07-18 21:10:32 |
合計ジャッジ時間 | 15,858 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 7 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 52 ms
5,376 KB |
testcase_10 | AC | 45 ms
5,376 KB |
testcase_11 | AC | 31 ms
5,376 KB |
testcase_12 | AC | 52 ms
5,376 KB |
testcase_13 | AC | 8 ms
5,376 KB |
testcase_14 | AC | 37 ms
5,376 KB |
testcase_15 | AC | 75 ms
5,376 KB |
testcase_16 | AC | 88 ms
5,504 KB |
testcase_17 | AC | 117 ms
6,912 KB |
testcase_18 | AC | 64 ms
7,040 KB |
testcase_19 | AC | 70 ms
6,912 KB |
コンパイルメッセージ
warning: unused import: `std::collections::*` --> src/main.rs:2:5 | 2 | use std::collections::*; | ^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::io::BufRead` --> src/main.rs:4:5 | 4 | use std::io::BufRead; | ^^^^^^^^^^^^^^^^ warning: unused imports: `Add`, `Sub` --> src/main.rs:6:16 | 6 | use std::ops::{Add, Sub}; | ^^^ ^^^ warning: function `read` is never used --> src/main.rs:24:4 | 24 | fn read<T: FromStr>() -> T { | ^^^^ | = note: `#[warn(dead_code)]` on by default warning: field `n` is never read --> src/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
ソースコード
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); }