verify/yukicoder/no_649_fenwick_tree/src/main.rs

View this file on GitHub
Last update: 2025-01-19 12:17:00+09:00
Problem: https://yukicoder.me/problems/no/649

Depends on

crates/data_structure/fenwick_tree/src/lib.rs

Code

// verification-helper: PROBLEM https://yukicoder.me/problems/no/649

use fenwick_tree::FenwickTree;
use proconio::{fastout, input};

#[derive(Debug, Clone, Copy)]
enum Query {
    Add(u64),
    Ask,
}

#[fastout]
fn main() {
    input! {
        q: usize,
        k: i32,
    }
    let mut queries = vec![];
    for _ in 0..q {
        input! {
            t: usize,
        }
        match t {
            1 => {
                input! {
                    a: u64,
                }
                queries.push(Query::Add(a));
            }
            2 => {
                queries.push(Query::Ask);
            }
            _ => unreachable!(),
        }
    }
    let queries = queries;
    let mut num_list = queries
        .iter()
        .filter_map(|q| {
            if let Query::Add(a) = q {
                Some(*a)
            } else {
                None
            }
        })
        .collect::<Vec<_>>();
    num_list.sort();
    num_list.dedup();
    let num_list = num_list;
    let mut fenwick = FenwickTree::new(num_list.len(), 0_i32);
    let mut sum = 0;
    for query in queries {
        match query {
            Query::Add(a) => {
                let idx = num_list.binary_search(&a).unwrap();
                fenwick.add(idx, 1);
                sum += 1;
            }
            Query::Ask => {
                if sum < k {
                    println!("-1");
                } else {
                    let id = fenwick.lower_bound(k);
                    println!("{}", num_list[id]);
                    fenwick.add(id, -1);
                    sum -= 1;
                }
            }
        }
    }
}

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