# Cod sursa(job #2728367)

Utilizator Data 23 martie 2021 09:51:56 Zeap 50 rs done Arhiva de probleme 6.89 kb
``````use std::cmp::Reverse;
use std::collections::BTreeSet;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;
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>;
}

struct FastSolution {
a: BTreeSet<i32>,
h: BinaryHeap<Reverse<i32>>,
c: HashMap<i32, i32>,
}

impl FastSolution {
fn new() -> Self {
Self {
a: BTreeSet::new(),
h: BinaryHeap::new(),
c: HashMap::new(),
}
}

fn add_diff(&mut self, d: i32) {
self.h.push(Reverse(d));
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;
}
None => {}
}
}
}

impl Solution for FastSolution {
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() {
}
if let Some(before) = self.a.range((Unbounded, Excluded(x))).rev().next() {
}
}
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))).rev().next() {
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))).rev().next() {
}
}
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 {
loop {
if let Some(head) = self.h.peek() {
self.h.pop();
} else {
break;
}
} else {
break;
}
}
self.h.peek().map(|h| h.0)
}
}
}
}
}

struct SlowSolution {
a: BTreeSet<i32>,
}

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

impl Solution for SlowSolution {
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_ {
println!(">>> {:?}", x);
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 = FastSolution::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 {
}

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

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),
}
}
}
``````