結果
| 問題 |
No.3017 交互浴
|
| コンテスト | |
| ユーザー |
 magurofly
|
| 提出日時 | 2025-01-25 14:42:04 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 509 ms / 2,000 ms |
| コード長 | 11,533 bytes |
| コンパイル時間 | 14,570 ms |
| コンパイル使用メモリ | 389,436 KB |
| 実行使用メモリ | 15,428 KB |
| 最終ジャッジ日時 | 2025-01-25 23:27:43 |
| 合計ジャッジ時間 | 41,379 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 55 |
コンパイルメッセージ
warning: unused imports: `HashMap` and `HashSet`
--> src/main.rs:3:24
|
3 | use std::collections::{HashMap, HashSet};
| ^^^^^^^ ^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `proconio::marker::Chars`
--> src/main.rs:6:5
|
6 | use proconio::marker::Chars;
| ^^^^^^^^^^^^^^^^^^^^^^^
warning: constant `INF` is never used
--> src/main.rs:8:7
|
8 | const INF: i64 = 1_000_000_000_000_000_000;
| ^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(non_snake_case)]
use std::collections::{HashMap, HashSet};
use proconio::input;
use proconio::marker::Chars;
const INF: i64 = 1_000_000_000_000_000_000;
fn main() {
input! {
N: usize,
H: [usize; N],
}
let mut borders = H.clone();
borders.push(0);
borders.sort();
borders.dedup();
let A = (0 .. borders.len() - 1).map(|i| (0, borders[i + 1] - borders[i]) ).collect::<Vec<_>>();
let mut seg = SegTree::<M>::from(A);
for i in 0 .. N {
let index = borders.binary_search(&H[i]).unwrap();
seg.apply_range(.. index, &Some(if i % 2 == 0 { true } else { false }));
println!("{}", seg.all_prod().0);
}
}
struct M;
impl SegTreeHelper for M {
type F = Option<bool>;
// (cyan_count, count)
type S = (usize, usize);
fn e() -> Self::S {
(0, 0)
}
fn op(&x: &Self::S, &y: &Self::S) -> Self::S {
(x.0 + y.0, x.1 + y.1)
}
fn map(&f: &Self::F, &x: &Self::S) -> Self::S {
if let Some(b) = f {
if b {
(x.1, x.1)
} else {
(0, x.1)
}
} else {
x
}
}
fn compose(&f: &Self::F, &g: &Self::F) -> Self::F {
g.or(f)
}
fn id() -> Self::F {
None
}
}
use segtree::*;
pub mod segtree {
// Update: 2022-10-29 12:45
#[allow(unused_variables)]
pub trait SegTreeHelper {
/// 要素の型
type S: Clone;
/// 要素の二項演算
fn op(x: &Self::S, y: &Self::S) -> Self::S;
/// 要素の単位元
fn e() -> Self::S;
/// 作用の型（使わない場合は `()` とする）
type F: Clone + Default;
/// 要素に作用させる
fn map(f: &Self::F, x: &Self::S) -> Self::S { x.clone() }
/// 作用の単位元
fn id() -> Self::F { Self::F::default() }
/// 作用の合成
fn compose(f: &Self::F, g: &Self::F) -> Self::F { g.clone() }
/// 再計算が必要か
fn is_failed(x: &Self::S) -> bool { false }
}
pub struct SegTree<H: SegTreeHelper> {
len: usize,
size: usize,
log: u32,
data: UnsafeCell<Vec<H::S>>,
lazy: UnsafeCell<Vec<H::F>>,
}
impl<H: SegTreeHelper> SegTree<H> {
/// 長さが `len` 、要素が全て `H::e()` となるセグメント木を作成する。
pub fn new(len: usize) -> Self {
assert!(len > 0);
let size = len.next_power_of_two();
let log = size.trailing_zeros();
Self {
len, size, log,
data: UnsafeCell::new(vec![H::e(); size * 2]),
lazy: UnsafeCell::new(vec![H::id(); size]),
}
}
/// `p` 番目の要素を取得する。
pub fn get(&self, p: usize) -> H::S { self[p].clone() }
/// `p` 番目の要素に `x` を代入する。
pub fn set(&mut self, mut p: usize, x: H::S) {
assert!(p < self.len);
p += self.size;
for i in (1 ..= self.log).rev() { self.push(p >> i); }
self.data_mut()[p] = x;
for i in 1 ..= self.log { self.update(p >> i); }
}
/// `range` に含まれる要素の積を取得する。
pub fn prod(&self, range: impl RangeBounds<usize>) -> H::S {
let (mut l, mut r) = self.range(range);
assert!(l <= r);
assert!(r <= self.len);
l += self.size;
r += self.size;
if l == r { return H::e(); }
for i in (1 ..= self.log).rev() {
if (l >> i) << i != l { self.push(l >> i); }
if (r >> i) << i != r { self.push(r - 1 >> i); }
}
let mut x = H::e();
let mut y = H::e();
while l < r {
if l & 1 != 0 {
x = H::op(&x, &self.data()[l]);
l += 1;
}
l >>= 1;
if r & 1 != 0 {
y = H::op(&self.data()[r - 1], &y);
}
r >>= 1;
}
H::op(&x, &y)
}
/// 全体の積を取得する。
pub fn all_prod(&self) -> H::S { self.data()[1].clone() }
/// `p` 番目の要素に `f` を適用する。
pub fn apply(&mut self, p: usize, f: &H::F) {
assert!(p < self.len);
let x = H::map(f, &self[p]);
self.set(p, x);
}
/// `range` に含まれる要素に `f` を適用する。
pub fn apply_range(&mut self, range: impl RangeBounds<usize>, f: &H::F) {
let (mut l, mut r) = self.range(range);
assert!(l <= r);
assert!(r <= self.len);
l += self.size;
r += self.size;
for i in (1 ..= self.log).rev() {
if (l >> i) << i != l { self.push(l >> i); }
if (r >> i) << i != r { self.push(r - 1 >> i); }
}
let (l, r) = {
let (l2, r2) = (l, r);
while l < r {
if l & 1 != 0 {
self.all_apply(l, f);
l += 1;
}
l >>= 1;
if r & 1 != 0 {
self.all_apply(r - 1, f);
}
r >>= 1;
}
(l2, r2)
};
for i in 1 ..= self.log {
if (l >> i) << i != l { self.update(l >> i); }
if (r >> i) << i != r { self.update(r - 1 >> i); }
}
}
pub fn max_right(&self, mut l: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
assert!(l <= self.len);
assert!(predicate(&H::e()));
if l == self.len { return self.len; }
l += self.size;
for i in (1 ..= self.log).rev() { self.push(l >> i); }
let mut x = H::e();
loop {
l >>= l.trailing_zeros();
if !predicate(&H::op(&x, &self.data()[l])) {
while l < self.size {
self.push(l);
l *= 2;
let y = H::op(&x, &self.data()[l]);
if predicate(&y) {
x = y;
l += 1;
}
}
return l - self.size;
}
x = H::op(&x, &self.data()[l]);
l += 1;
if l.is_power_of_two() {
break;
}
}
self.len
}
pub fn min_left(&self, mut r: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
assert!(r <= self.len);
assert!(predicate(&H::e()));
if r == 0 { return 0; }
r += self.size;
for i in (1 ..= self.log).rev() { self.push(r - 1 >> i); }
let mut x = H::e();
loop {
r -= 1;
r >>= r.trailing_zeros();
if !predicate(&H::op(&self.data()[r], &x)) {
while r < self.size {
self.push(r);
r = 2 * r + 1;
let y = H::op(&self.data()[r], &x);
if predicate(&y) {
x = y;
r -= 1;
}
}
return r + 1 - self.size;
}
x = H::op(&self.data()[r], &x);
if r.is_power_of_two() {
break;
}
}
0
}
fn update(&self, k: usize) {
let z = H::op(&self.data()[k * 2], &self.data()[k * 2 + 1]);
self.data_mut()[k] = z;
}
fn all_apply(&self, k: usize, f: &H::F) {
let y = H::map(f, &self.data()[k]);
self.data_mut()[k] = y;
if k < self.size {
let h = H::compose(&self.lazy()[k], f);
self.lazy_mut()[k] = h;
if H::is_failed(&self.data()[k]) {
self.push(k);
self.update(k);
}
}
}
fn push(&self, k: usize) {
self.all_apply(2 * k, &self.lazy()[k]);
self.all_apply(2 * k + 1, &self.lazy()[k]);
self.lazy_mut()[k] = H::id();
}
fn range(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
use Bound::*;
(match range.start_bound() { Included(&p) => p, Excluded(&p) => p + 1, Unbounded => 0 },
match range.end_bound() { Included(&p) => p + 1, Excluded(&p) => p, Unbounded => self.len })
}
fn data(&self) -> &Vec<H::S> { unsafe { &*self.data.get() } }
fn lazy(&self) -> &Vec<H::F> { unsafe { &*self.lazy.get() } }
fn data_mut(&self) -> &mut Vec<H::S> { unsafe { &mut *self.data.get() } }
fn lazy_mut(&self) -> &mut Vec<H::F> { unsafe { &mut *self.lazy.get() } }
}
impl<H: SegTreeHelper> From<Vec<H::S>> for SegTree<H> {
fn from(xs: Vec<H::S>) -> Self {
let this = Self::new(xs.len());
for (p, x) in xs.into_iter().enumerate() {
this.data_mut()[this.size + p] = x;
}
for k in (1 .. this.size).rev() { this.update(k); }
this
}
}
impl<H: SegTreeHelper> FromIterator<H::S> for SegTree<H> {
fn from_iter<T: IntoIterator<Item = H::S>>(iter: T) -> Self {
Self::from(iter.into_iter().collect::<Vec<_>>())
}
}
impl<H: SegTreeHelper> Index<usize> for SegTree<H> {
type Output = H::S;
fn index(&self, mut p: usize) -> &H::S {
assert!(p < self.len);
p += self.size;
for i in (1 ..= self.log).rev() { self.push(p >> i); }
&self.data()[p]
}
}
impl<H: SegTreeHelper> Debug for SegTree<H> where H::S: Debug, H::F: Debug {
fn fmt(&self, f: &mut Formatter<'_>) -> Result {
f.write_fmt(format_args!("len={}, size={}, log={}, e={:?}, id={:?}\n", self.len, self.size, self.log, H::e(), H::id()))?;
let data_str = self.data().iter().map(|x| format!("{:?}", x)).collect::<Vec<_>>();
let lazy_str = self.lazy().iter().map(|x| format!("({:?})", x)).collect::<Vec<_>>();
let unit_width = lazy_str.iter().chain(data_str.iter()).map(String::len).max().unwrap();
fn print_row(f: &mut Formatter<'_>, raw_row: &[String], pad: usize) -> Result {
let mut row = vec![];
for raw in raw_row { row.push(format!("{:^width$}", raw, width=pad)); }
f.write_str("|")?;
f.write_str(&row.join("|"))?;
f.write_str("|\n")
}
for i in 0 .. self.log {
print_row(f, &data_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
print_row(f, &lazy_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
}
print_row(f, &data_str[self.size ..], unit_width)?;
Ok(())
}
}
use std::{cell::*, fmt::*, iter::*, ops::*};
}