Cod sursa(job #2729039)

Utilizator wickedmanCristian Strat wickedman Data 24 martie 2021 00:19:57
Problema Zeap Scor 70
Compilator rs Status done
Runda Arhiva de probleme Marime 11.63 kb
use std::cmp;
use std::collections::{BTreeMap, BTreeSet};
use std::fs::File;
use std::io::prelude::*;
use std::io::{self, BufRead, BufWriter};
use std::ops::Bound::{Excluded, Unbounded};
use std::path::Path;

#[derive(Debug)]
enum Command {
    Insert(i32),
    Delete(i32),
    Lookup(i32),
    QueryMaxDiff,
    QueryMinDiff,
}

trait Solution {
    fn execute(&mut self, cmd: Command) -> Option<i32>;
}

const RANGE: i32 = 1_000_000_000;
// const RANGE: i32 = 8;
const DEBUG: bool = false;

#[derive(Clone, Debug)]
struct NodeAgg {
    min: i32,
    max: i32,
    min_diff: i32,
    set: bool,
}

impl NodeAgg {
    fn default() -> Self {
        Self {
            set: false,
            max: 0,
            min: RANGE,
            min_diff: RANGE,
        }
    }
}

struct Node {
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
    lo: i32,
    hi: i32,
    agg: NodeAgg,
}

impl Node {
    fn new(lo: i32, hi: i32) -> Self {
        Self {
            left: None,
            right: None,
            lo,
            hi,
            agg: NodeAgg {
                min: RANGE,
                min_diff: RANGE,
                max: 0,
                set: false,
            },
        }
    }
    #[inline]
    fn mid(&self) -> i32 {
        self.lo + (self.hi - self.lo) / 2
    }

    fn is_leaf(&self) -> bool {
        self.lo == self.hi
    }

    fn update(&mut self, x: i32, set: bool) -> bool {
        if self.is_leaf() {
            if self.agg.set == set {
                return false;
            }
            self.agg = match set {
                true => NodeAgg {
                    set,
                    max: x,
                    min: x,
                    min_diff: RANGE,
                },
                false => NodeAgg::default(),
            };
            return true;
        }
        let left_range = (0..=self.mid()).contains(&x);
        let did_update = match (left_range, self.left.as_mut(), self.right.as_mut()) {
            (true, Some(child), _) | (false, _, Some(child)) => child.update(x, set),
            (true, None, _) => {
                self.left = Some(Box::new(Node::new(self.lo, self.mid())));
                self.left.as_mut().unwrap().update(x, set)
            }
            (false, _, None) => {
                self.right = Some(Box::new(Node::new(self.mid() + 1, self.hi)));
                self.right.as_mut().unwrap().update(x, set)
            }
        };
        if did_update {
            self.update_agg();
        }
        did_update
    }

    fn update_agg(&mut self) {
        self.agg = match (self.left.as_ref(), self.right.as_ref()) {
            (Some(left), Some(right)) => NodeAgg {
                set: left.agg.set || right.agg.set,
                max: cmp::max(left.agg.max, right.agg.max),
                min: cmp::min(left.agg.min, right.agg.min),
                min_diff: self.compute_min_diff(&left.agg, &right.agg),
            },
            (Some(child), None) | (None, Some(child)) => child.agg.clone(),
            (None, None) => NodeAgg::default(),
        }
    }

    #[inline]
    fn compute_min_diff(&self, l: &NodeAgg, r: &NodeAgg) -> i32 {
        let mut res = cmp::min(l.min_diff, r.min_diff);
        if l.set && r.set {
            res = cmp::min(res, r.min - l.max)
        }
        res
    }

    fn has(&self, x: i32) -> bool {
        if !self.agg.set {
            false
        } else if self.is_leaf() {
            true
        } else {
            match (
                (0..=self.mid()).contains(&x),
                self.left.as_ref(),
                self.right.as_ref(),
            ) {
                (true, Some(child), _) | (false, _, Some(child)) => child.has(x),
                _ => false,
            }
        }
    }

    #[inline]
    fn opt_bound(bound: i32) -> Option<i32> {
        match bound {
            0 | RANGE => None,
            x => Some(x),
        }
    }

    fn max(&self) -> Option<i32> {
        Self::opt_bound(self.agg.max)
    }

    fn min(&self) -> Option<i32> {
        Self::opt_bound(self.agg.min)
    }

    fn min_diff(&self) -> Option<i32> {
        Self::opt_bound(self.agg.min_diff)
    }

    fn print(&self, indent: &String) {
        println!("{}{}..{} {:?}", indent, self.lo, self.hi, self.agg);
        let new_indent = format!("{}\t", indent);
        if let Some(left) = self.left.as_ref() {
            println!("{}left:", indent);
            left.print(&new_indent);
        }
        if let Some(right) = self.right.as_ref() {
            println!("{}right:", indent);
            right.print(&new_indent);
        }
    }
}

struct IntervalTreeSolution {
    root: Node,
}

impl IntervalTreeSolution {
    fn new() -> Self {
        Self {
            root: Node::new(1, RANGE),
        }
    }
}

impl Solution for IntervalTreeSolution {
    fn execute(&mut self, cmd: Command) -> Option<i32> {
        use Command::*;
        let res = match cmd {
            Insert(x) => {
                self.root.update(x, true);
                None
            }
            Delete(x) => match self.root.update(x, false) {
                true => None,
                false => Some(-1),
            },
            Lookup(x) => match self.root.has(x) {
                true => Some(1),
                false => Some(0),
            },
            QueryMaxDiff => match (self.root.min(), self.root.max()) {
                (Some(a), Some(b)) if a != b => Some(b - a),
                _ => Some(-1),
            },
            QueryMinDiff => Some(self.root.min_diff().unwrap_or(-1)),
        };
        if DEBUG {
            println!(">>> {:?} > {:?}", cmd, res);
            self.root.print(&"".to_string());
        }
        res
    }
}

struct BTreeSolution {
    a: BTreeSet<i32>,
    c: BTreeMap<i32, i32>,
}

impl BTreeSolution {
    fn new() -> Self {
        BTreeSolution {
            a: BTreeSet::new(),
            c: BTreeMap::new(),
        }
    }

    fn add_diff(&mut self, d: i32) {
        match self.c.get_mut(&d) {
            Some(v) => {
                *v += 1;
            }
            None => {
                self.c.insert(d, 1);
            }
        }
    }

    fn rem_diff(&mut self, d: i32) {
        match self.c.get_mut(&d) {
            Some(v) => {
                *v -= 1;
                if *v == 0 {
                    self.c.remove(&d);
                }
            }
            None => {}
        }
    }
}

impl Solution for BTreeSolution {
    fn execute(&mut self, cmd: Command) -> Option<i32> {
        use Command::*;
        match cmd {
            Insert(x) => {
                if self.a.insert(x) {
                    if let Some(after) = self.a.range((Excluded(x), Unbounded)).next() {
                        self.add_diff(after - x)
                    }
                    if let Some(before) = self.a.range((Unbounded, Excluded(x))).next_back() {
                        self.add_diff(x - before)
                    }
                }
                None
            }
            Delete(x) => match self.a.remove(&x) {
                true => {
                    if let Some(after) = self.a.range((Excluded(x), Unbounded)).next() {
                        self.rem_diff(after - x)
                    }
                    if let Some(before) = self.a.range((Unbounded, Excluded(x))).next_back() {
                        self.rem_diff(x - before);
                    }
                    if let Some(after) = self.a.range((Excluded(x), Unbounded)).next() {
                        if let Some(before) = self.a.range((Unbounded, Excluded(x))).next_back() {
                            self.add_diff(after - before)
                        }
                    }
                    None
                }
                false => Some(-1),
            },
            Lookup(x) => match self.a.contains(&x) {
                true => Some(1),
                false => Some(0),
            },
            QueryMaxDiff => match (self.a.iter().next(), self.a.iter().next_back()) {
                (Some(a), Some(b)) if a != b => Some(b - a),
                _ => Some(-1),
            },
            QueryMinDiff => {
                if self.a.len() < 2 {
                    Some(-1)
                } else {
                    self.c.iter().next().map(|kv| *kv.0)
                }
            }
        }
    }
}

struct BruteForceSolution {
    a: BTreeSet<i32>,
}

impl BruteForceSolution {
    fn new() -> Self {
        BruteForceSolution { a: BTreeSet::new() }
    }
}

impl Solution for BruteForceSolution {
    fn execute(&mut self, cmd: Command) -> Option<i32> {
        use Command::*;
        match cmd {
            Insert(x) => {
                self.a.insert(x);
                None
            }
            Delete(x) => match self.a.remove(&x) {
                true => None,
                false => Some(-1),
            },
            Lookup(x) => match self.a.contains(&x) {
                true => Some(1),
                false => Some(0),
            },
            QueryMaxDiff => match (self.a.iter().next(), self.a.iter().next_back()) {
                (Some(a), Some(b)) if a != b => Some(b - a),
                _ => Some(-1),
            },
            QueryMinDiff => {
                let mut best: Option<i32> = None;
                let mut last: Option<i32> = None;
                for crt in self.a.iter() {
                    if let Some(last) = last.as_mut() {
                        if let Some(best) = best.as_mut() {
                            if *best > *crt - *last {
                                *best = *crt - *last;
                            }
                        } else {
                            best = Some(*crt - *last);
                        }
                        *last = *crt;
                    } else {
                        last = Some(*crt);
                    }
                }
                Some(best.unwrap_or(-1))
            }
        }
    }
}

fn run<S: Solution>(s: &mut S, in_: &mut Input, out: &mut Output) {
    for x in in_ {
        if let Some(y) = s.execute(x) {
            out.put(y);
        }
    }
    out.done();
}

fn main() {
    let mut input = Input::from_path("zeap.in");
    let mut output = Output::from_path("zeap.out");
    // let mut sol = SlowSolution::new();
    let mut sol = IntervalTreeSolution::new();
    run(&mut sol, &mut input, &mut output);
}

struct Output {
    out: io::BufWriter<File>,
}

impl Output {
    fn from_path<P>(filename: P) -> Self
    where
        P: AsRef<Path>,
    {
        let file = File::create(filename).expect("failed to open output");
        Self {
            out: BufWriter::new(file),
        }
    }

    fn put(&mut self, x: i32) {
        write!(self.out, "{}\n", x);
    }

    fn done(&mut self) {
        self.out.flush().expect("failed to close output")
    }
}

struct Input {
    lines: io::Lines<io::BufReader<File>>,
}

impl Input {
    fn from_path<P>(filename: P) -> Self
    where
        P: AsRef<Path>,
    {
        let file = File::open(filename).expect("failed to open input");
        Self {
            lines: io::BufReader::new(file).lines(),
        }
    }
}

impl Iterator for Input {
    type Item = Command;

    fn next(&mut self) -> Option<Command> {
        let line = self.lines.next()?.ok()?;
        let args: Vec<_> = line.split(" ").collect();
        let op = args[0];
        let op_arg = args.get(1).map(|x_str| x_str.parse::<i32>().ok());
        match (op, op_arg) {
            ("I", Some(Some(x))) => Some(Command::Insert(x)),
            ("S", Some(Some(x))) => Some(Command::Delete(x)),
            ("C", Some(Some(x))) => Some(Command::Lookup(x)),
            ("MAX", None) => Some(Command::QueryMaxDiff),
            ("MIN", None) => Some(Command::QueryMinDiff),
            _ => panic!("couldn't parse input {:?}", line),
        }
    }
}