結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー ikdikd
提出日時 2021-12-07 22:41:21
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 789 ms / 2,000 ms
コード長 6,466 bytes
コンパイル時間 14,102 ms
コンパイル使用メモリ 388,448 KB
実行使用メモリ 62,164 KB
最終ジャッジ日時 2024-07-08 02:11:19
合計ジャッジ時間 24,863 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

//! # Bundled libraries
//!
//! - `ceil_log2 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b60dc67706797611e680510aa6492f6397a2e104)`              licensed under **missing** as `crate::__cargo_equip::crates::__ceil_log2_0_1_0`
//! - `input_i_scanner 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b60dc67706797611e680510aa6492f6397a2e104)`        licensed under **missing** as `crate::__cargo_equip::crates::input_i_scanner`
//! - `lowest_common_ancestor 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#b60dc67706797611e680510aa6492f6397a2e104)` licensed under **missing** as `crate::__cargo_equip::crates::lowest_common_ancestor`

pub use __cargo_equip::prelude::*;

use input_i_scanner::InputIScanner;
use lowest_common_ancestor::LowestCommonAncestor;
use std::collections::HashMap;

fn main() {
    let stdin = std::io::stdin();
    let mut _i_i = InputIScanner::from(stdin.lock());

    macro_rules! scan {
        (($($t: ty),+)) => {
            ($(scan!($t)),+)
        };
        ($t: ty) => {
            _i_i.scan::<$t>() as $t
        };
        (($($t: ty),+); $n: expr) => {
            std::iter::repeat_with(|| scan!(($($t),+))).take($n).collect::<Vec<_>>()
        };
        ($t: ty; $n: expr) => {
            std::iter::repeat_with(|| scan!($t)).take($n).collect::<Vec<_>>()
        };
    }

    let (n, q) = scan!((usize, usize));
    let s = scan!(String);
    let s: Vec<char> = std::iter::once('^').chain(s.chars()).collect();

    let mut stack = Vec::new();
    stack.push(0);
    let mut parent = vec![0; n + 1];
    let mut lr_pos = HashMap::new();
    let mut rl_pos = HashMap::new();
    for i in 1..=n {
        if s[i] == '(' {
            stack.push(i);
        } else {
            let j = stack.pop().unwrap();
            let opt = lr_pos.insert(j, i);
            assert!(opt.is_none());
            let opt = rl_pos.insert(i, j);
            assert!(opt.is_none());
            parent[j] = stack.last().copied().unwrap();
        }
    }
    assert_eq!(stack, vec![0]);
    let mut edges = Vec::new();
    for i in 1..=n {
        if s[i] == '(' {
            edges.push((parent[i], i));
            edges.push((parent[i], lr_pos[&i]));
        }
    }
    let lca = LowestCommonAncestor::new(n + 1, edges.iter().copied());

    for _ in 0..q {
        let (x, y) = scan!((usize, usize));
        let x = if s[x] == '(' { x } else { rl_pos[&x] };
        let y = if s[y] == '(' { y } else { rl_pos[&y] };
        let ans_l = lca.get(x, y);
        if ans_l == 0 {
            println!("-1");
        } else {
            println!("{} {}", ans_l, lr_pos[&ans_l]);
        }
    }
}

// The following code was expanded by `cargo-equip`.

#[rustfmt::skip]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __ceil_log2_0_1_0 {pub trait CeilLog2{fn ceil_log2(self)->Self;}macro_rules!impl_ceil_log2{($($t:ty),+)=>{$(impl CeilLog2 for$t{fn ceil_log2(self)->Self{assert!(self>=1);let mut x=0;let mut pow_2_x=1;while pow_2_x<self{x+=1;pow_2_x=pow_2_x.saturating_mul(2);}x}})+};}impl_ceil_log2!(usize,u32,u64);}
        pub mod input_i_scanner {use std::fmt;use std::io;use std::str;pub struct InputIScanner<R>{r:R,l:String,i:usize,}impl<R:io::BufRead>InputIScanner<R>{pub fn new(reader:R)->Self{Self{r:reader,l:String::new(),i:0,}}pub fn scan<T>(&mut self)->T where T:str::FromStr,<T as str::FromStr>::Err:fmt::Debug,{self.skip_blanks();assert!(self.i<self.l.len());assert_ne!(&self.l[self.i..=self.i]," ");let rest=&self.l[self.i..];let len=rest.find(' ').unwrap_or_else(| |rest.len());let val=rest[..len].parse().unwrap_or_else(|e|panic!("{:?}, attempt to read `{}`",e,rest));self.i+=len;val}fn skip_blanks(&mut self){loop{match self.l[self.i..].find(|ch|ch!=' '){Some(j)=>{self.i+=j;break;}None=>{let mut buf=String::new();let num_bytes=self.r.read_line(&mut buf).unwrap_or_else(|_|panic!("invalid UTF-8"));assert!(num_bytes>0,"reached EOF :(");self.l=buf.trim_end_matches('\n').trim_end_matches('\r').to_string();self.i=0;}}}}}impl<'a>From<&'a str>for InputIScanner<&'a[u8]>{fn from(s:&'a str)->Self{Self::new(s.as_bytes())}}impl<'a>From<io::StdinLock<'a> >for InputIScanner<io::BufReader<io::StdinLock<'a> > >{fn from(stdin:io::StdinLock<'a>)->Self{Self::new(io::BufReader::new(stdin))}}}
        pub mod lowest_common_ancestor {use crate::__cargo_equip::preludes::lowest_common_ancestor::*;use ceil_log2::CeilLog2;pub struct LowestCommonAncestor{ancestor:Vec<Vec<usize> >,depth:Vec<usize>,}const ILLEGAL:usize=std::usize::MAX;impl LowestCommonAncestor{pub fn new(n:usize,edges:impl Iterator<Item=(usize,usize)>)->Self{let mut g=vec![vec![];n];for(u,v)in edges{g[u].push(v);g[v].push(u);}let mut depth=vec![0;n];let mut parent=vec![ILLEGAL;n];let mut stack=vec![(0,ILLEGAL)];while let Some((u,p))=stack.pop(){for&v in&g[u]{if v!=p{depth[v]=depth[u]+1;parent[v]=u;stack.push((v,u));}}}let table_size=n.ceil_log2().max(1);let mut ancestor=vec![vec![ILLEGAL;n];table_size];ancestor[0]=parent;for i in 1..table_size{ancestor[i]=(0..n).map(|v|{if ancestor[i-1][v]==ILLEGAL{ILLEGAL}else{ancestor[i-1][ancestor[i-1][v]]}}).collect();}Self{ancestor,depth}}pub fn get(&self,u:usize,v:usize)->usize{assert!(u<self.depth.len());assert!(v<self.depth.len());let(mut u,mut v)=if self.depth[u]>=self.depth[v]{(u,v)}else{(v,u)};assert!(self.depth[u]>=self.depth[v]);let depth_diff=self.depth[u]-self.depth[v];for i in 0..self.ancestor.len(){if depth_diff>>i&1==1{u=self.ancestor[i][u];}}if u==v{return u;}for i in(0..self.ancestor.len()).rev(){if self.ancestor[i][u]!=self.ancestor[i][v]{u=self.ancestor[i][u];v=self.ancestor[i][v];}}let lca=self.ancestor[0][u];assert_ne!(lca,ILLEGAL);lca}pub fn get_dist(&self,u:usize,v:usize)->usize{let w=self.get(u,v);self.depth[u]+self.depth[v]-self.depth[w]*2}pub fn depth(&self,u:usize)->usize{self.depth[u]}pub fn ancestor(&self,i:usize,u:usize)->Option<usize>{if i>=self.ancestor.len(){None}else{let a=self.ancestor[i][u];if a==ILLEGAL{None}else{Some(a)}}}}}
    }

    pub(crate) mod macros {
        pub mod __ceil_log2_0_1_0 {}
        pub mod input_i_scanner {}
        pub mod lowest_common_ancestor {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __ceil_log2_0_1_0 {}
        pub mod input_i_scanner {}
        pub mod lowest_common_ancestor {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__ceil_log2_0_1_0 as ceil_log2;}
    }
}
0