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