結果
問題 | No.1705 Mode of long array |
ユーザー |
|
提出日時 | 2021-10-09 01:53:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 49 ms / 3,000 ms |
コード長 | 5,829 bytes |
コンパイル時間 | 14,980 ms |
コンパイル使用メモリ | 394,588 KB |
実行使用メモリ | 12,304 KB |
最終ジャッジ日時 | 2024-07-23 11:09:12 |
合計ジャッジ時間 | 19,290 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
コンパイルメッセージ
warning: unused variable: `n` --> src/main.rs:3:10 | 3 | let (n, m) : (usize, usize) = input_t(); | ^ help: if this is intentional, prefix it with an underscore: `_n` | = note: `#[warn(unused_variables)]` on by default
ソースコード
fn main() {let (n, m) : (usize, usize) = input_t();let a : Vec<usize> = input_vec();def_monoid!(M,(usize,usize), (0,0), |a:&(usize,usize),b:&(usize,usize)| a.clone().max(b.clone()));let mut seg = SegmentTree::<M>::from( &(0..m).map(|i| (a[i],i)).collect::<Vec<_>>() );let q : usize = input();let mut ans = vec![];for _ in 0..q {let (t, x, y) : (usize,usize,usize) = input_t3();match t {1 => { let t = seg.get(x-1); seg.set(x-1, (t.0 + y, t.1)); }2 => { let t = seg.get(x-1); seg.set(x-1, (t.0 - y, t.1)); }3 => { let t = seg.fold(..); ans.push(t.1 + 1); }_ => unreachable!()}}println!("{}", ans.into_iter().map(|a| a.to_string()).collect::<Vec<_>>().join("\n"));}#[macro_export]macro_rules! def_monoid { ($m:ident, $t:ty, $id:expr, $op:expr) => { pub struct $m; impl Monoid for $m { type Type = $t; fn identity() -> Self::Type{ $id } fn operator(x:&Self::Type, y:&Self::Type) -> Self::Type {$op(x, y) } }}; }pub trait Monoid { type Type: Copy + Clone + std::fmt::Debug; fn identity() -> Self::Type; fn operator(a: &Self::Type, b: &Self::Type) -> Self::Type;}struct SegmentTree<T : Monoid> { n : usize, seg: Vec<T::Type>, }#[allow(unused)]impl<T: Monoid> SegmentTree<T> {pub fn new(n : usize) -> Self { SegmentTree {n, seg:vec![T::identity(); 2*n + 1]} }pub fn from(s : &[T::Type]) -> Self {let n = s.len();let mut seg = vec![T::identity(); 2*n+1];for (i, &si) in s.iter().enumerate() { seg[i+n] = si; }for i in (1..n).rev() { seg[i] = T::operator(&seg[2*i], &seg[2*i+1]); }SegmentTree {n,seg}}pub fn set(&mut self, i:usize, x:T::Type) {let mut index = i + self.n;self.seg[index] = x;while index > 0 {index /= 2;self.seg[index] = T::operator(&self.seg[2*index], &self.seg[2*index+1]);}}fn _fold(&self, mut l:usize, mut r:usize) -> T::Type {let mut left = T::identity();let mut right = T::identity();while l < r {if l%2 == 1 { left = T::operator(&self.seg[l], &left); l+=1; }if r%2 == 1 { r-=1; right = T::operator(&right, &self.seg[r]); }l/=2; r/=2;}T::operator(&left, &right)}pub fn fold<R:std::ops::RangeBounds<usize>>(&self, range: R) -> T::Type {let l = self.n + match range.start_bound() {std::ops::Bound::Unbounded => 0,std::ops::Bound::Included(&l) => l,_ => unreachable!()};let r = self.n + match range.end_bound() {std::ops::Bound::Unbounded => self.n,std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};self._fold(l, r)}pub fn get(&self, index:usize) -> T::Type { self.seg[index + self.n].clone() }fn _first_left<F: Fn(&T::Type)->bool>(&self, mut l:usize, r:usize, f : F) -> Option<usize> {if !f(&self.fold(l..r)) { return None; }l += self.n;loop {if f(&self.seg[l]) {if l >= self.n { return Some(l - self.n); }l *= 2;} else {if l%2 == 0 { l += 1; }else { l = l/2 + 1; }}}}pub fn first_left<R: std::ops::RangeBounds<usize>, F: Fn(&T::Type)->bool>(&self, range : R, f : F) -> Option<usize> {let l = match range.start_bound() {std::ops::Bound::Unbounded => 0,std::ops::Bound::Included(&l) => l,_ => unreachable!()};let r = match range.end_bound() {std::ops::Bound::Unbounded => self.n,std::ops::Bound::Included(&x) => x + 1,std::ops::Bound::Excluded(&x) => x,};self._first_left(l, r, f)}}#[allow(dead_code)]fn input<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}#[allow(dead_code)]fn input_t<T: std::str::FromStr, U: std::str::FromStr>() -> (T, U) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap())}#[allow(dead_code)]fn input_t3<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr>() -> (T1, T2, T3) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap())}#[allow(dead_code)]fn input_t4<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr>() -> (T1, T2, T3, T4) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap())}#[allow(dead_code)]fn input_t5<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr, T5: std::str::FromStr>() -> (T1, T2, T3, T4,T5) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap(), s[4].parse().ok().unwrap())}#[allow(dead_code)]fn input_vec<T: std::str::FromStr>() -> Vec<T> {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect()}