K-th Largest Triplet の解説

Aiは1..=iの中の要素についてAi番目という意味。

ということで、後ろから前に考えていけば残った配列についての何番目ということになるので、

あとは、残った配列についてのnthの検索とnthの削除がうまくできればよい。 これはhttps://judge.yosupo.jp/problem/ordered_set

をacできるものがあれば対応できます。

fn main() {
    input! {
        n: usize,
        mut p: [Usize1; n]
    }
    p.reverse();
    let mut ans = vec![usize::MAX; n];
    let mut set = OrderedSet::from(&(0..n).collect_vec());
    for i in 0..n {
        set.insert(i);
    }
    for (idx, &num) in p.iter().enumerate() {
        let nth = set.get_nth(num).unwrap();
        ans[nth] = n - idx;
        set.remove(nth);
    }
    println!("{}", ans.iter().join(" "));
}

https://github.com/k-ohnuma/k-ohnuma-procon-lib/blob/main/src/data_structure/ordered_set.rs