結果
| 問題 | No.318 学学学学学 |
| ユーザー |
 pianoneko
|
| 提出日時 | 2019-08-08 17:15:42 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 133 ms / 2,000 ms |
| コード長 | 7,569 bytes |
| コンパイル時間 | 13,029 ms |
| コンパイル使用メモリ | 383,216 KB |
| 実行使用メモリ | 13,112 KB |
| 最終ジャッジ日時 | 2024-07-18 20:40:39 |
| 合計ジャッジ時間 | 17,510 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
コンパイルメッセージ
warning: unused import: `std::io::BufRead`
--> src/main.rs:4:5
|
4 | use std::io::BufRead;
| ^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused imports: `Add`, `Sub`
--> src/main.rs:6:16
|
6 | use std::ops::{Add, Sub};
| ^^^ ^^^
warning: function `read` is never used
--> src/main.rs:24:4
|
24 | fn read<T: FromStr>() -> T {
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
use std::cmp::*;use std::collections::*;use std::fmt::Debug;use std::io::BufRead;use std::io::{stdin, Read};use std::ops::{Add, Sub};use std::str::FromStr;#[derive(Eq, PartialEq, Clone, Debug)]pub struct Rev<T>(pub T);impl<T: PartialOrd> PartialOrd for Rev<T> {fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {other.0.partial_cmp(&self.0)}}impl<T: Ord> Ord for Rev<T> {fn cmp(&self, other: &Rev<T>) -> Ordering {other.0.cmp(&self.0)}}fn read<T: FromStr>() -> T {let stdin = stdin();let stdin = stdin.lock();let token: String = stdin.bytes().map(|c| c.expect("failed to read char") as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();token.parse().ok().expect("failed to parse token")}macro_rules! read {(($($t:tt),*)) => {( $(read!($t)),* )};([[$t:tt; $len1:expr]; $len2:expr]) => {(0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()};([$t:tt; $len:expr]) => {(0..$len).map(|_| read!($t)).collect::<Vec<_>>()};(chars) => {read!(String).chars().collect::<Vec<char>>()};(usize1) => {read!(usize) - 1};($t:ty) => {{let stdin = stdin();let stdin = stdin.lock();let token: String = stdin.bytes().map(|c| c.unwrap() as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();token.parse::<$t>().unwrap()}};}macro_rules! input {(mut $name:ident: $t:tt, $($r:tt)*) => {let mut $name = read!($t);$(println!("{}", stringify!($r));)*input!($($r)*);};(mut $name:ident: $t:tt) => {let mut $name = read!($t);};($name:ident: $t:tt, $($r:tt)*) => {let $name = read!($t);input!($($r)*);};($name:ident: $t:tt) => {let $name = read!($t);};}trait VecExt {fn cumulation(&self) -> Vec<i64>;fn cumulation_query(&self, a: usize, b: usize) -> i64;}impl VecExt for Vec<i64> {fn cumulation(&self) -> Vec<i64> {let mut vec = vec![0; self.len() + 1];for i in 0..self.len() {vec[i + 1] = self[i] + vec[i];}return vec;}fn cumulation_query(&self, left: usize, right: usize) -> i64 {return self[right] - self[left];}}pub trait Monoid {type T: Copy + Clone + std::fmt::Debug + PartialOrd + std::fmt::Display;fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T;fn identity() -> Self::T;}pub trait OperatorMonoid {type T;type U: Copy + Clone + std::fmt::Debug + PartialOrd;fn op1(lhs: &Self::U, rhs: &Self::U) -> Self::U;fn op2(lhs: &Self::T, rhs: &Self::U, len: &usize) -> Self::T;fn identity() -> Self::U;}#[derive(Clone)]struct Max {}impl Monoid for Max {type T = i64;fn identity() -> Self::T {return 0}fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T {return std::cmp::max(*lhs, *rhs);}}#[derive(Clone)]struct OperatorMax {}impl OperatorMonoid for OperatorMax {type T = i64;type U = Option<i64>;fn identity() -> Self::U {return None;}fn op1(_query: &Self::U, rhs: &Self::U) -> Self::U {return *rhs}fn op2(lhs: &Self::T, rhs: &Self::U, _: &usize) -> Self::T {if rhs.is_some() {(*rhs).unwrap()} else {*lhs}}}#[derive(Clone)]struct Min {}impl Monoid for Min {type T = i64;fn identity() -> Self::T {return (1 << 31) - 1}fn op(lhs: &Self::T, rhs: &Self::T) -> Self::T {return std::cmp::min(*lhs, *rhs);}}#[derive(Clone)]struct OperatorMin {}impl OperatorMonoid for OperatorMin {type T = i64;type U = Option<i64>;fn identity() -> Self::U {return None;}fn op1(_query: &Self::U, rhs: &Self::U) -> Self::U {return *rhs}fn op2(lhs: &Self::T, rhs: &Self::U, _: &usize) -> Self::T {if rhs.is_some() {(*rhs).unwrap()} else {*lhs}}}#[derive(Debug)]pub struct LazySegmentTree<M: Monoid, O: OperatorMonoid<T = M::T>> {n: usize,size: usize,data: Vec<M::T>,lazy: Vec<O::U>,}impl<M: Monoid, O: OperatorMonoid<T = M::T>> LazySegmentTree<M, O> {pub fn new(n: usize) -> LazySegmentTree<M, O> {let mut size = 1;while size < n {size *= 2;}LazySegmentTree {n: n,size: size,data: vec![M::identity(); size * 2],lazy: vec![O::identity(); size * 2],}}pub fn set(&mut self, k: usize, v: M::T) {self.data[k + self.size] = v;}pub fn build(&mut self) {for k in (1..self.size - 1).rev() {self.data[k] = M::op(&self.data[k * 2], &self.data[k * 2 + 1]);}}pub fn propagate(&mut self, k: usize, len: usize) {if self.lazy[k] != O::identity() {if k < self.size {self.lazy[2 * k + 0] = O::op1(&self.lazy[2 * k + 0], &self.lazy[k]);self.lazy[2 * k + 1] = O::op1(&self.lazy[2 * k + 1], &self.lazy[k]);}self.data[k] = O::op2(&self.data[k], &self.lazy[k], &len);self.lazy[k] = O::identity();}}pub fn _update(&mut self, a: usize, b: usize, x: O::U, k: usize, l: usize, r: usize) {self.propagate(k, r - l);if r <= a || b <= l {return;} else if a <= l && r <= b {self.lazy[k] = O::op1(&self.lazy[k], &x);self.propagate(k, r - l);} else {self._update(a, b, x, 2 * k + 0, l, (l + r) >> 1);self._update(a, b, x, 2 * k + 1, (l + r) >> 1, r);self.data[k] = M::op(&self.data[2 * k + 0], &self.data[2 * k + 1]);}}pub fn update(&mut self, a: usize, b: usize, x: O::U) {let sz = self.size;self._update(a, b, x, 1, 0, sz);}fn _query(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> M::T {self.propagate(k, r - l);if r <= a || b <= l {return M::identity();} else if a <= l && r <= b {return self.data[k];} else {return M::op(&self._query(a, b, 2 * k + 0, l, (l + r) >> 1),&self._query(a, b, 2 * k + 1, (l + r) >> 1, r),);}}pub fn query(&mut self, a: usize, b: usize) -> M::T {let sz = self.size;return self._query(a, b, 1, 0, sz);}pub fn debug(&self) {for i in 0..self.n {print!("{} ", self.data[i + self.size]);}println!();}}use std::collections::BTreeSet;fn main() {input!(n: usize, a: [i64; n]);let mut set = BTreeSet::new();let mut map_l = HashMap::new();let mut map_r = HashMap::new();let mut seg: LazySegmentTree<Max, OperatorMax> = LazySegmentTree::new(n);for i in 0..n {set.insert(a[i]);map_r.insert(a[i], i);map_l.insert(a[n - i - 1], n - i - 1);}for x in set.iter() {seg.update(*map_l.get(&x).unwrap(), *map_r.get(&x).unwrap() + 1, Some(*x));}for i in 0..n {print!("{} " , seg.query(i, i + 1));}println!();}