結果

問題 No.1703 Much Matching
ユーザー phsplsphspls
提出日時 2022-10-02 02:08:22
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 1,342 bytes
コンパイル時間 594 ms
コンパイル使用メモリ 148,212 KB
実行使用メモリ 17,576 KB
最終ジャッジ日時 2023-08-25 22:10:18
合計ジャッジ時間 5,659 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 0 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 1 ms
4,380 KB
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 WA -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 WA -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 WA -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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