結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-07-29 18:08:54 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 3,858 bytes |
コンパイル時間 | 12,933 ms |
コンパイル使用メモリ | 378,152 KB |
実行使用メモリ | 6,816 KB |
最終ジャッジ日時 | 2024-07-02 15:25:04 |
合計ジャッジ時間 | 16,788 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
//---------- begin SegmentTree Range update Point query ---------- mod segment_tree { pub struct RUPQ<T, F> { n: usize, b: usize, a: Vec<T>, id: T, op: F, } impl<T: Copy, F: Fn(T, T) -> T> RUPQ<T, F> { pub fn new(n: usize, id: T, op: F) -> RUPQ<T, F> { let mut k = 0; while (1 << k) < n { k += 1; } RUPQ { n: 1 << k, b: k, a: vec![id; 2 << k], id: id, op: op, } } fn down(&mut self, x: usize) { let k = x + self.n; let a = &mut self.a; for i in (1..(self.b + 1)).rev() { let y = k >> i; a[2 * y] = (self.op)(a[2 * y], a[y]); a[2 * y + 1] = (self.op)(a[2 * y + 1], a[y]); a[y] = self.id; } } pub fn update(&mut self, mut l: usize, mut r: usize, v: T) { self.down(l); self.down(r - 1); l += self.n; r += self.n; let a = &mut self.a; while l < r { if (l & 1) == 1 { a[l] = (self.op)(a[l], v); l += 1; } if (r & 1) == 1 { r -= 1; a[r] = (self.op)(a[r], v); } l >>= 1; r >>= 1; } } pub fn find(&mut self, mut x: usize) -> T { x += self.n; let mut y = self.a[x]; x >>= 1; while x > 0 { y = (self.op)(y, self.a[x]); x >>= 1; } y } } } //---------- end SegmentTree Range update Point query ---------- //https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ここまで fn run() { input! { n: usize, a: [u32; n], } let mut b = vec![(0, 0); n]; for (i, x) in a.into_iter().enumerate() { b[i] = (x, i); } b.sort(); fn assign(a: u32, b: u32) -> u32 { if b == 0 { a } else { b } } let mut s = segment_tree::RUPQ::new(n, 0, assign); for i in 0..n { if i + 1 < n && b[i].0 == b[i + 1].0 { s.update(b[i].1, b[i + 1].1 + 1, b[i].0); } else { s.update(b[i].1, b[i].1 + 1, b[i].0); } } let mut ans = String::new(); for i in 0..n { ans.push_str(&s.find(i).to_string()); ans.push(' '); } ans.pop(); println!("{}", ans); } fn main() { run(); }