AtCoder Beginner Contest 433 E

https://atcoder.jp/contests/abc433/tasks/abc433_e

小さい値から行列の要素を埋めていけばよいです。行と列の片方にその値があればどちらかを適当に埋めていけばいいのですが、両方にある場合は交わった要素をその値にしなければなりません。
また、それ以外のその値以下で使われていない最大の値にすればよいです。それにはBTreeSetを使って要素を[first, last)の区間にすればよいです。結果的に区間が隣り合えば結合します。

// Max Matrix 2
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Test = (Vec<i32>, Vec<i32>);
type Matrix = Vec<Vec<i32>>;

fn read_test() -> Test {
    let _s: String = read();
    let X: Vec<i32> = read_vec();
    let Y: Vec<i32> = read_vec();
    (X, Y)
}

fn print_mat(A: &Matrix) {
    for v in A {
        let w = v.iter().map(|a| a.to_string()).collect::<Vec<String>>();
        println!("{}", w.join(" "))
    }
}

type Range = (i32, i32);

use std::collections::{BTreeSet, BTreeMap};

// x以下で範囲に含まれない最小の値
fn max_value(x: i32, tree: &BTreeSet<Range>) -> i32 {
    let before = tree.range(..=(x, i32::MAX)).next_back();
    if let Some(&(first, last)) = before {
        // 直前の区間が x を覆っているなら
        if first <= x && x < last {
            first - 1
        }
        else {
            x
        }
    }
    else {
        x
    }
}

fn insert(tree: &mut BTreeSet<Range>, x: i32) {
    let mut new_first = x;
    let mut new_last = x + 1;
    // 左にある区間のうち、開始点が x 以下で最大のもの
    let left = tree.range(..=(x, i32::MAX)).next_back().cloned();
    if let Some((first, last)) = left {
        if last >= new_first {
            // 隣接 or 重複
            tree.remove(&(first, last));
            new_first = new_first.min(first);
            new_last = new_last.max(last);
        }
    }
    
    // 右側の区間で、開始点が x+1 以上の最初の区間
    let right = tree.range((x+1, 0)..).next().cloned();
    if let Some((first, last)) = right {
        if first <= new_last {
            // 隣接 or 重複
            tree.remove(&(first, last));
            new_first = new_first.min(first);
            new_last = new_last.max(last);
        }
    }
    
    tree.insert((new_first, new_last));
}

fn frequency(A: &Vec<i32>) -> Vec<(i32, Vec<usize>)> {
    let mut freq: BTreeMap<i32, Vec<usize>> = BTreeMap::new();
    for (i, &a) in A.iter().enumerate() {
        let e = freq.entry(a).or_insert(vec![]);
        (*e).push(i)
    }
    freq.into_iter().collect::<Vec<_>>()
}

fn collect(X: Vec<i32>, Y: Vec<i32>) -> Vec<(i32, usize, usize, u32)> {
    let mut results: Vec<(i32, usize, usize, u32)> = vec![];
    let freq_X = frequency(&X);
    let freq_Y = frequency(&Y);
    let mut k: usize = 0;
    let mut l: usize = 0;
    let L1 = freq_X.len();
    let L2 = freq_Y.len();
    while k < L1 && l < L2 {
        let (n1, xs) = &freq_X[k];
        let (n2, ys) = &freq_Y[l];
        if *n1 == *n2 {
            for &x in xs.iter() {
                for &y in ys.iter() {
                    results.push((*n1, x, y, 3))
                }
            }
            k += 1;
            l += 1
        }
        else if *n1 < *n2 {
            for &x in xs.iter() {
                results.push((*n1, x, 0, 1))
            }
            k += 1
        }
        else {
            for &y in ys.iter() {
                results.push((*n2, 0, y, 2))
            }
            l += 1
        }
    }
    
    while k < L1 {
        let (n1, xs) = &freq_X[k];
        for &x in xs.iter() {
            results.push((*n1, x, 0, 1))
        }
        k += 1
    }
    while l < L2 {
        let (n2, ys) = &freq_Y[l];
        for &y in ys.iter() {
            results.push((*n2, 0, y, 2))
        }
        l += 1
    }
    results
}

fn F_each((X, Y): Test) -> Option<Matrix> {
    let N = X.len();
    let M = Y.len();
    let v = collect(X, Y);
    let mut A: Matrix = vec![vec![0; M]; N];
    let mut used: BTreeSet<Range> = BTreeSet::new();
    for (n, x0, y0, flag) in v {
        if flag == 3 {
            let m = max_value(n, &used);
            if m == 0 {
                return None
            }
            A[x0][y0] = m;
            insert(&mut used, m)
        }
        if (flag & 1) == 1 {
            for j in 0..M {
                if A[x0][j] == 0 {
                    let m = max_value(n, &used);
                    if m == 0 {
                        return None
                    }
                    A[x0][j] = m;
                    insert(&mut used, m)
                }
            }
            if (0..M).map(|j| A[x0][j]).max() != Some(n) {
                return None
            }
        }
        if (flag & 2) == 2 {
            for j in 0..N {
                if A[j][y0] == 0 {
                    let m = max_value(n, &used);
                    if m == 0 {
                        return None
                    }
                    A[j][y0] = m;
                    insert(&mut used, m)
                }
            }
            if (0..N).map(|j| A[j][y0]).max() != Some(n) {
                return None
            }
        }
    }
    Some(A)
}

fn F(T: usize) {
    for _ in 0..T {
        let test = read_test();
        match F_each(test) {
            Some(A) => { println!("Yes"); print_mat(&A) },
            None    => println!("No")
        }
    }
}

fn main() {
    let T: usize = read();
    F(T)
}