結果
| 問題 |
No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
|
| コンテスト | |
| ユーザー |
 pianoneko
|
| 提出日時 | 2019-08-08 22:00:25 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
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);
}