結果
問題 | No.1778 括弧列クエリ / Bracketed Sequence Query |
ユーザー | ikd |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 301 ms
6,812 KB |
testcase_01 | AC | 272 ms
6,816 KB |
testcase_02 | AC | 302 ms
6,940 KB |
testcase_03 | AC | 262 ms
6,940 KB |
testcase_04 | AC | 284 ms
6,944 KB |
testcase_05 | AC | 261 ms
24,540 KB |
testcase_06 | AC | 163 ms
6,944 KB |
testcase_07 | AC | 21 ms
13,180 KB |
testcase_08 | AC | 634 ms
58,248 KB |
testcase_09 | AC | 61 ms
21,404 KB |
testcase_10 | AC | 257 ms
45,540 KB |
testcase_11 | AC | 211 ms
30,260 KB |
testcase_12 | AC | 283 ms
24,672 KB |
testcase_13 | AC | 643 ms
56,848 KB |
testcase_14 | AC | 224 ms
41,128 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 662 ms
58,512 KB |
testcase_17 | AC | 624 ms
58,640 KB |
testcase_18 | AC | 614 ms
58,520 KB |
testcase_19 | AC | 633 ms
58,512 KB |
testcase_20 | AC | 622 ms
58,516 KB |
testcase_21 | AC | 1 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 680 ms
50,448 KB |
testcase_24 | AC | 789 ms
62,164 KB |
testcase_25 | AC | 762 ms
62,164 KB |
testcase_26 | AC | 474 ms
57,472 KB |
testcase_27 | AC | 359 ms
57,480 KB |
ソースコード
//! # 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;} } }