use std::io; #[derive(Clone)] struct Range { first: i64, last: i64, } impl Range { fn new(first: i64, last: i64) -> Self { assert!(first <= last); Self { first, last } } fn contains(&self, value: i64) -> bool { value >= self.first && value <= self.last } fn len(&self) -> i64 { 1 + self.last - self.first } } fn in_ranges(ranges: &Vec, value: i64) -> bool { for range in ranges { if range.contains(value) { return true; } } false } fn merge_or_add(ranges: &mut Vec, range: &Range) { if range.len() == 0 { return; } let i = ranges.partition_point(|x| x.last < range.first); if i == ranges.len() { ranges.push(range.clone()); return; } if ranges[i].first > range.last { ranges.insert(i, range.clone()); return; } if ranges[i].contains(range.first) { if ranges[i].contains(range.last) { // Whole range is swallowed return; } merge_or_add(ranges, &Range::new(ranges[i].last + 1, range.last)); return; } if ranges[i].contains(range.last) { ranges.insert(i, Range::new(range.first, ranges[i].first - 1)); return; } let before = Range::new(range.first, ranges[i].first - 1); let after = Range::new(ranges[i].last + 1, range.last); ranges.insert(i, before); merge_or_add(ranges, &after); } fn remove_overlap(ranges: &Vec) -> Vec { let mut ret = Vec::new(); for range in ranges { merge_or_add(&mut ret, range); } ret } fn main() { let mut ranges = Vec::new(); loop { let mut buffer = String::new(); let bytes = io::stdin().read_line(&mut buffer).unwrap(); if bytes == 0 || buffer == "\n" { break; } let mut iter = buffer.trim_end().split('-'); let first = iter.next().unwrap().parse::().unwrap(); let last = iter.next().unwrap().parse::().unwrap(); ranges.push(Range::new(first, last)); } ranges.sort_by(|a, b| a.first.cmp(&b.first)); let mut available = Vec::new(); loop { let mut buffer = String::new(); let bytes = io::stdin().read_line(&mut buffer).unwrap(); if bytes == 0 { break; } available.push(buffer.trim_end().parse::().unwrap()); } let mut fresh = 0; for ingredient in available { if in_ranges(&ranges, ingredient) { fresh += 1; } } println!("Fresh ingrediences {}", fresh); let ranges2 = remove_overlap(&ranges); let mut fresh2 = 0; for range in ranges2 { fresh2 += range.len(); } println!("Fresh ids {}", fresh2); }