結果

問題 No.1332 Range Nearest Query
ユーザー LyricalMaestro
提出日時 2025-02-06 00:55:40
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 924 ms / 2,500 ms
コード長 3,657 bytes
コンパイル時間 15,158 ms
コンパイル使用メモリ 400,788 KB
実行使用メモリ 94,508 KB
最終ジャッジ日時 2025-02-06 00:56:36
合計ジャッジ時間 42,118 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `n`
   --> src/main.rs:111:9
    |
111 |     let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    |         ^ help: if this is intentional, prefix it with an underscore: `_n`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable `L` should have a snake case name
  --> src/main.rs:87:17
   |
87 |         let mut L = self.size + l;
   |                 ^ help: convert the identifier to snake case: `l`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `R` should have a snake case name
  --> src/main.rs:88:17
   |
88 |         let mut R = self.size + r;
   |                 ^ help: convert the identifier to snake case: `r`

ソースコード

diff # 

use std::io::{self, BufRead};

const MAX_INT: i64 = i64::MAX;

struct SegmentTree {
    size: usize,
    array: Vec<Vec<i64>>,
}

impl SegmentTree {
    fn new(init_array: &[i64]) -> Self {
        let mut n = 1;
        while n < init_array.len() {
            n *= 2;
        }
        let mut array = vec![Vec::new(); 2 * n];
        for (i, &a) in init_array.iter().enumerate() {
            array[n + i].push(a);
        }
        
        let mut tree = SegmentTree { size: n, array };
        tree.build();
        tree
    }

    fn build(&mut self) {
        let mut end_index = self.size;
        let mut start_index = end_index / 2;
        while start_index >= 1 {
            for i in start_index..end_index {
                self.merge(i);
            }
            end_index = start_index;
            start_index /= 2;
        }
    }

    fn merge(&mut self, node: usize) {
        let (left, right) = (node * 2, node * 2 + 1);
        let (l, r) = (&self.array[left], &self.array[right]);
        let (mut li, mut ri) = (0, 0);
        let mut merged = Vec::with_capacity(l.len() + r.len());
        
        while li < l.len() || ri < r.len() {
            if li == l.len() {
                merged.push(r[ri]);
                ri += 1;
            } else if ri == r.len() {
                merged.push(l[li]);
                li += 1;
            } else if l[li] <= r[ri] {
                merged.push(l[li]);
                li += 1;
            } else {
                merged.push(r[ri]);
                ri += 1;
            }
        }
        self.array[node] = merged;
    }

    fn calc(&self, array: &[i64], x: i64) -> i64 {
        if array.is_empty() {
            return MAX_INT;
        }
        if x <= array[0] {
            return array[0] - x;
        }
        if x >= array[array.len() - 1] {
            return x - array[array.len() - 1];
        }
        
        let mut low = 0;
        let mut high = array.len() - 1;
        while high - low > 1 {
            let mid = (high + low) / 2;
            if array[mid] <= x {
                low = mid;
            } else {
                high = mid;
            }
        }
        (x - array[low]).min(array[high] - x)
    }

    fn get_abs_min(&self, l: usize, r: usize, x: i64) -> i64 {
        let mut L = self.size + l;
        let mut R = self.size + r;
        let mut s = MAX_INT;
        
        while L < R {
            if R & 1 != 0 {
                R -= 1;
                s = s.min(self.calc(&self.array[R], x));
            }
            if L & 1 != 0 {
                s = s.min(self.calc(&self.array[L], x));
                L += 1;
            }
            L /= 2;
            R /= 2;
        }
        s
    }
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    
    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let x: Vec<i64> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    
    let q: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let mut queries = Vec::with_capacity(q);
    
    for _ in 0..q {
        let parts: Vec<i64> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        queries.push((parts[0] as usize - 1, parts[1] as usize - 1, parts[2]));
    }
    
    let seg_tree = SegmentTree::new(&x);
    for (l, r, x) in queries {
        let ans = seg_tree.get_abs_min(l, r + 1, x);
        println!("{}", ans);
    }
}
0