2019 JUST Programming Contest B. Memory Management System
問題
長さ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() } }