/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 6ms 540.0 KiB
#4 Accepted 13ms 512.0 KiB
#5 Accepted 97ms 836.0 KiB
#6 Accepted 67ms 1.137 MiB
#7 Accepted 72ms 1.227 MiB
#8 Accepted 64ms 1.277 MiB
#9 Accepted 71ms 1.234 MiB
#10 Accepted 80ms 1.895 MiB
#11 Accepted 68ms 3.617 MiB
#12 Accepted 100ms 3.211 MiB
#13 Accepted 101ms 16.688 MiB
#14 Accepted 124ms 16.523 MiB
#15 Accepted 129ms 16.637 MiB
#16 Accepted 134ms 17.902 MiB
#17 Accepted 82ms 16.574 MiB
#18 Accepted 29ms 532.0 KiB
#19 Accepted 91ms 1.52 MiB
#20 Accepted 1ms 284.0 KiB
#21 Accepted 21ms 628.0 KiB
#22 Accepted 20ms 328.0 KiB
#23 Accepted 86ms 16.559 MiB
#24 Accepted 98ms 17.895 MiB
#25 Accepted 97ms 17.98 MiB
#26 Accepted 133ms 16.445 MiB

Code

use std::collections::BTreeSet;
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock().lines();
    let t: usize = input.next().unwrap().unwrap().trim().parse().unwrap();
    
    for _ in 0..t {
        let n: usize = input.next().unwrap().unwrap().trim().parse().unwrap();
        let mut vec = Vec::new();
        let mut id = Vec::new();

        for _ in 0..n {
            let line = input.next().unwrap().unwrap();
            let parts: Vec<i32> = line.trim().split_whitespace()
                                       .map(|x| x.parse::<i32>().unwrap())
                                       .collect();
            let l = parts[0];
            let r = parts[1];
            vec.push((r, l)); // Push as (end, start)
            id.push(l);
        }

        vec.sort(); // Sort by end, then start
        id.sort();  // Sort by start
        let mut cur = 0;
        let mut st = BTreeSet::new();
        let mut res = Vec::new();

        for &id_val in &id {
            if id_val > cur {
                cur = id_val;
            } else {
                cur += 1;
            }
            st.insert(cur);
            res.push(cur);
        }

        let mut valid = true;
        for &(cur_r, cur_l) in &vec {
            let it = st.range(cur_l..).next().cloned();
            if let Some(&val) = it.as_ref() {
                if val > cur_r || val < cur_l {
                    valid = false;
                    break;
                }
                st.remove(&val);
            } else {
                valid = false;
                break;
            }
        }

        if !valid {
            println!("NO");
        } else {
            println!("YES");
            println!("{}", res.iter().map(|x| x.to_string()).collect::<Vec<String>>().join(" "));
        }
    }
}

Information

Submit By
Type
Submission
Problem
P1185 I. Segment
Language
Rust 2021 (Rust 1.75.0)
Submit At
2025-03-25 08:58:37
Judged At
2025-03-25 08:58:37
Judged By
Score
100
Total Time
134ms
Peak Memory
17.98 MiB