結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー wass80
提出日時 2020-08-03 17:35:23
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,372 bytes
記録
コンパイル時間 14,065 ms
コンパイル使用メモリ 386,132 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-13 11:11:48
合計ジャッジ時間 17,313 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 13 RE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: method `select` is never used
   --> src/main.rs:115:8
    |
61  | impl<T: Clone + Debug> SegTree<T> {
    | --------------------------------- method in this implementation
...
115 |     fn select(&self, i: usize) -> &T {
    |        ^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

ソースコード

diff #
raw source code 

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::fmt::Debug;
struct SegTree<T: Clone + Debug> {
    data: Vec<T>,
    size: usize,
    zero: T,
    mapped: fn(&T, &T) -> T,
}
impl<T: Clone + Debug> SegTree<T> {
    /*
    8 elements
    1
    2         3
    4    5    6    7
    8 9  A B  C D  E F
      <-        <-
    */
    fn new(size: usize, zero: T, mapped: fn(&T, &T) -> T) -> SegTree<T> {
        let mut data = vec![];
        for _ in 0..2 * size + 1 {
            data.push(zero.clone())
        }
        SegTree {
            data: data,
            size: size,
            zero: zero,
            mapped: mapped,
        }
    }
    fn fold(&self, l: usize, r: usize) -> T {
        let mut fl = self.zero.clone();
        let mut fr = self.zero.clone();
        let mut l = l + self.size;
        let mut r = r + self.size;
        /*
            1:
            2:            3:0
            4:1    5:2    6:X    7:X

        */
        while l < r {
            if l & 1 == 1 {
                fl = (self.mapped)(&self.data[l], &fl);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                fr = (self.mapped)(&fr, &self.data[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.mapped)(&fl, &fr)
    }
    fn update(&mut self, i: usize, x: T) {
        let mut i = i + self.size;
        self.data[i] = x;
        while i > 1 {
            i >>= 1;
            self.data[i] = (self.mapped)(&self.data[i << 1], &self.data[(i << 1) + 1])
        }
    }
    fn select(&self, i: usize) -> &T {
        &self.data[i + self.size]
    }
}

fn main() {
    input! {
        n: usize, q:usize,
        query: [(usize, i64, i64); q]
    }
    use std::cmp;
    let inf = (1 << 31) - 1;
    let mut seg = SegTree::new(n, inf, |x, y| cmp::min(*x, *y));
    for (com, x, y) in query {
        if com == 1 {
            seg.update(x as usize, y);
        } else {
            println!("{}", seg.fold(x as usize, y as usize));
        }
    }
}
0