結果

問題 No.1703 Much Matching
ユーザー phspls
提出日時 2022-10-02 02:08:22
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,342 bytes
コンパイル時間 14,649 ms
コンパイル使用メモリ 379,392 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-12-24 09:02:18
合計ジャッジ時間 19,028 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 5 RE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

const INF: usize = 1usize << 60;

fn upper_bound(target: &Vec<usize>, val: usize) -> usize {
    let mut upper = target.len();
    let mut lower = 0usize;
    while upper > lower {
        let middle = (upper + lower) / 2;
        if target[middle] > val {
            upper = middle;
        } else {
            lower = middle + 1;
        }
    }
    upper
}

fn main() {
    let mut nmq = String::new();
    std::io::stdin().read_line(&mut nmq).ok();
    let nmq: Vec<usize> = nmq.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let n = nmq[0];
    let m = nmq[1];
    let q = nmq[2];
    let queries = (0..q).map(|_| {
            let mut temp = String::new();
            std::io::stdin().read_line(&mut temp).ok();
            let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
            (temp[0]-1, temp[1]-1)
        })
        .collect::<Vec<(usize, usize)>>();

    let mut mdp = vec![INF; n+1];
    let mut wdp = vec![INF; m+1];
    mdp[0] = 0;
    wdp[0] = 0;
    let mut result = 0usize;
    for &(a, b) in queries.iter() {
        let midx = upper_bound(&mdp, a);
        let widx = upper_bound(&wdp, b);
        result = result.max(midx.min(widx));
        mdp[midx] = mdp[midx].min(a);
        wdp[widx] = wdp[widx].min(b);
    }
    println!("{}", result);
}
0