#706357 (Rust) No.1705 Mode of long array

• 問題: No.1705 Mode of long array
• ユーザー: 👑 zeronosu77108
• 提出日時: 2021-10-09 01:53:45
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 48 ms / 3,000 ms
• コード長: 5,829 bytes
• コンパイル時間: 2,829 ms
• コンパイル使用メモリ: 154,572 KB
• 実行使用メモリ: 12,312 KB
• 最終ジャッジ日時: 2023-09-30 17:26:57
• 合計ジャッジ時間: 8,966 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	3 ms; 4,380 KB
testcase_07	AC	4 ms; 4,376 KB
testcase_08	AC	4 ms; 4,380 KB
testcase_09	AC	3 ms; 4,380 KB
testcase_10	AC	3 ms; 4,380 KB
testcase_11	AC	4 ms; 4,376 KB
testcase_12	AC	4 ms; 4,380 KB
testcase_13	AC	40 ms; 6,540 KB
testcase_14	AC	29 ms; 5,124 KB
testcase_15	AC	31 ms; 4,376 KB
testcase_16	AC	37 ms; 4,464 KB
testcase_17	AC	27 ms; 4,380 KB
testcase_18	AC	22 ms; 4,380 KB
testcase_19	AC	41 ms; 4,984 KB
testcase_20	AC	25 ms; 4,380 KB
testcase_21	AC	31 ms; 5,884 KB
testcase_22	AC	44 ms; 7,292 KB
testcase_23	AC	27 ms; 4,376 KB
testcase_24	AC	27 ms; 4,376 KB
testcase_25	AC	27 ms; 4,380 KB
testcase_26	AC	27 ms; 4,376 KB
testcase_27	AC	27 ms; 4,380 KB
testcase_28	AC	27 ms; 4,376 KB
testcase_29	AC	27 ms; 4,380 KB
testcase_30	AC	27 ms; 4,380 KB
testcase_31	AC	27 ms; 4,380 KB
testcase_32	AC	27 ms; 4,376 KB
testcase_33	AC	44 ms; 7,248 KB
testcase_34	AC	44 ms; 7,324 KB
testcase_35	AC	45 ms; 7,332 KB
testcase_36	AC	44 ms; 7,340 KB
testcase_37	AC	45 ms; 7,324 KB
testcase_38	AC	48 ms; 7,396 KB
testcase_39	AC	45 ms; 7,356 KB
testcase_40	AC	46 ms; 7,340 KB
testcase_41	AC	45 ms; 7,376 KB
testcase_42	AC	43 ms; 7,328 KB
testcase_43	AC	44 ms; 12,260 KB
testcase_44	AC	43 ms; 12,196 KB
testcase_45	AC	44 ms; 12,200 KB
testcase_46	AC	43 ms; 12,312 KB
testcase_47	AC	44 ms; 12,152 KB
testcase_48	AC	45 ms; 12,180 KB
testcase_49	AC	45 ms; 7,388 KB
testcase_50	AC	45 ms; 7,368 KB
testcase_51	AC	46 ms; 7,296 KB
testcase_52	AC	45 ms; 7,300 KB
testcase_53	AC	45 ms; 7,320 KB

コンパイルメッセージ

warning: unused variable: `n`
 --> 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

warning: 1 warning emitted

ソースコード

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()
}