verify/yosupo/range_kth_smallest/src/main.rs

View this file on GitHub
Last update: 2024-12-16 14:54:34+09:00
Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

crates/wavelet/wavelet_matrix/src/lib.rs

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/range_kth_smallest

use proconio::{fastout, input};
use wavelet_matrix::WaveletMatrix;

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        l_r_k: [(usize, usize, usize); q],
    }
    let sorted = {
        let mut ret = a.clone();
        ret.sort();
        ret.dedup();
        ret
    };
    let compressed: Vec<usize> = a
        .into_iter()
        .map(|x| sorted.binary_search(&x).unwrap())
        .collect();
    let wm = WaveletMatrix::new(&compressed);
    for (l, r, k) in l_r_k {
        let ans = wm.quantile(l..r, k);
        println!("{}", sorted[ans]);
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError