2019 JUST Programming Contest B. Memory Management System

問題

codeforces.com

長さmの線分がとn個の区間があります。q個のクエリが与えられます。i番目のクエリでは整数k_iが与えられるので、線分上のn個の区間と重ならない長さk_i以上の区間で最も右にあるものを出力してください。

解法

空の集合Sを用意する。空いている区間を長さで降順にソートして持っておく。クエリを先読みしてソートしておき、大きい方から見ていく。クエリの値がk_qのとき、k_q以上の長さの直線をSに入れ、Sの中の最も右にある区間を出力する。

コード

use std::io::{stdout, BufWriter, Write};

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner(s.lock());

    let t: usize = sc.read();
    for _ in 0..t {
        let n: usize = sc.read();
        let m: u32 = sc.read();
        let q: usize = sc.read();
        let mut segments = vec![];
        for _ in 0..n {
            let l = sc.read::<u32>() - 1;
            let r = sc.read::<u32>();
            segments.push((l, r));
        }
        segments.sort();

        let mut cur = 0;
        let mut free = vec![];
        for (l, r) in segments.into_iter() {
            if cur < l {
                free.push((cur, l));
            }
            cur = r;
        }
        if cur < m {
            free.push((cur, m));
        }

        let mut free_segments = vec![];
        for (l, r) in free.into_iter() {
            let length = r - l;
            free_segments.push((length, l, r));
        }
        free_segments.sort();

        let mut queries = vec![];
        for i in 0..q {
            let k = sc.read();
            queries.push((k, i));
        }
        queries.sort();
        queries.reverse();

        let mut ans: Vec<Option<(u32, u32)>> = vec![None; q];
        let mut top: Option<(_, _)> = None;
        for (required_length, i) in queries.into_iter() {
            while let Some((length, l, r)) = free_segments.pop() {
                if length >= required_length {
                    match top {
                        Some(cur) => {
                            if cur < (r, l) {
                                top = Some((r, l));
                            }
                        }
                        None => {
                            top = Some((r, l));
                        }
                    }
                } else {
                    free_segments.push((length, l, r));
                    break;
                }
            }

            if let Some((r, _)) = top {
                let l = r - required_length;
                ans[i] = Some((l, r));
            }
        }

        let out = stdout();
        let mut out = BufWriter::new(out.lock());
        for ans in ans.into_iter() {
            match ans {
                Some((l, r)) => {
                    write!(out, "{} {}", l + 1, r).unwrap();
                    out.write_all(b"\n").unwrap();
                }
                None => {
                    write!(out, "-1 -1").unwrap();
                    out.write_all(b"\n").unwrap();
                }
            }
        }
    }
}

pub struct Scanner<R>(R);

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}