#1085296 (Rust) No.3144 Parentheses Modification and Rotation (01 Ver.)

• 問題: No.3144 Parentheses Modification and Rotation (01 Ver.)
• ユーザー: magurofly
• 提出日時: 2025-05-16 22:07:25
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 50 ms / 2,000 ms
• コード長: 14,386 bytes
• コンパイル時間: 11,398 ms
• コンパイル使用メモリ: 400,732 KB
• 実行使用メモリ: 7,716 KB
• 最終ジャッジ日時: 2025-10-27 15:12:07
• 合計ジャッジ時間: 14,032 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
    input! {
      N: usize,
      S: Chars,
      R: usize, M: usize,
    }

    if N % 2 != 0 {
      say(-1);
      return;
    }

    let seg = SegTree::<H>::from((0 .. N).map(|i| if S[i] == '(' { (0, 1) }  else { (1, 0) } ).to_vec());

    let mut ans = INF;
    for rot in 0 .. N {
      let l = seg.prod(rot .. N);
      let r = seg.prod(0 .. rot);
      let (d, u) = H::op(&l, &r);
      let d2u = (d + 1) / 2;
      let u2d = (u + d % 2) / 2;
      ans.chmin(rot * R + (d2u + u2d) * M);
    }

    say(ans);
}

enum H {}
impl SegTreeHelper for H {
  type F = ();
  type S = (usize, usize);
  fn e() -> Self::S {
      (0, 0)
  }
  fn op(&(a, b): &Self::S, &(c, d): &Self::S) -> Self::S {
      (a + c.saturating_sub(b), d + b.saturating_sub(c))
  }
}

type Int = usize;
const MOD: Int = 998244353;
// const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];

use proconio::{input, input_interactive, marker::{Chars, Bytes, Usize1}};
use std::*;
use std::ops::*;
use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList
use cmp::{self, Reverse}; // cmp::{min, max}

fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
fn say<T: std::fmt::Display>(x: T) -> T { println!("{}", x); x }
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }

trait MyItertools : Iterator + Sized {
  fn to_vec(self) -> Vec<Self::Item> { self.collect::<Vec<_>>() }
  fn to_vec_rev(self) -> Vec<Self::Item> { let mut v = self.collect::<Vec<_>>(); v.reverse(); v }
  fn tally(self) -> HashMap<Self::Item, usize> where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts }
  fn count_if<P: Fn(Self::Item) -> bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() }
  fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) }
  fn mex(self, gen: impl IntoIterator<Item = Self::Item>) -> Self::Item where Self::Item: Ord { let mut v = self.collect::<Vec<_>>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() }
}
impl<T: ?Sized> MyItertools for T where T: Iterator + Sized {}

trait MyOrd : PartialOrd + Sized {
  fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } }
  fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } }
}
impl<T: Sized + PartialOrd> MyOrd for T {}

#[derive(Debug, Clone, Default)]
pub struct BTreeMultiset<T: Ord> { len: usize, set: BTreeMap<T, usize> }
impl<'a, T: Ord> BTreeMultiset<T> {
  pub fn new() -> Self { Self { len: 0, set: BTreeMap::new() } }
  pub fn len(&self) -> usize { self.len }
  pub fn count(&self, x: &T) -> usize { self.set.get(x).copied().unwrap_or(0) }
  pub fn insert_multiple(&mut self, x: T, count: usize) -> usize { self.len += count; let n = self.set.entry(x).or_insert(0); *n += count; *n }
  pub fn insert(&mut self, x: T) -> usize { self.insert_multiple(x, 1) }
  pub fn remove_multiple(&mut self, x: &T, count: usize) -> usize { if let Some(n) = self.set.get_mut(x) { let n0 = *n; *n = n0.saturating_sub(count); let n = *n; self.len -= n0 - n; if n == 0 { self.set.remove(x); } n } else { 0 } }
  pub fn remove(&mut self, x: &T) -> usize { self.remove_multiple(x, 1) }
  pub fn iter(&'a self) -> btree_map::Iter<'a, T, usize> { self.set.iter() }
  pub fn into_iter(self) -> btree_map::IntoIter<T, usize> { self.set.into_iter() }
  pub fn keys(&'a self) -> btree_map::Keys<'a, T, usize> { self.set.keys() }
  pub fn range(&'a self, range: impl RangeBounds<T>) -> btree_map::Range<'a, T, usize> { self.set.range(range) }
}

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::*};
}