Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3675

Problem Lang User Status Time Memory
Line Add Get Min rust sansen AC 155 ms 21.39 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
hand_max_00 AC 144 ms 19.16 MiB
max_random_00 AC 58 ms 12.65 MiB
max_random_01 AC 56 ms 12.65 MiB
max_random_02 AC 57 ms 12.65 MiB
parabola_random_00 AC 154 ms 21.32 MiB
parabola_random_01 AC 155 ms 21.33 MiB
parabola_random_02 AC 151 ms 21.39 MiB
random_00 AC 41 ms 8.98 MiB
random_01 AC 45 ms 9.62 MiB
random_02 AC 27 ms 5.87 MiB
small_00 AC 5 ms 0.55 MiB
small_01 AC 5 ms 0.63 MiB

mod lichao { use std; type T = i64; const INF: T = std::i64::MAX; #[derive(Clone, Copy)] pub struct Line(T, T); impl Line { fn eval(&self, x: T) -> T { self.0 * x + self.1 } } type Link = Option<Box<Node>>; struct Node { line: Line, left: Link, right: Link, } impl Node { fn find(node: &Link, left: T, right: T, x: T) -> T { let mut node = node; let mut ans = INF; let mut l = left; let mut r = right; while let Some(t) = node.as_ref() { ans = std::cmp::min(ans, t.line.eval(x)); let m = (l + r) / 2; node = if x < m { r = m; &t.left } else { l = m; &t.right }; } ans } fn insert(node: &mut Link, l: T, r: T, mut line: Line) { if node.is_none() { *node = Some(Box::new(Node { line: line, left: None, right: None, })); return; } let node = node.as_mut().unwrap(); if node.line.eval(l) > line.eval(l) { std::mem::swap(&mut node.line, &mut line); } let m = (l + r) / 2; if node.line.eval(r) <= line.eval(r) { return; } else if node.line.eval(m) <= line.eval(m) { Node::insert(&mut node.right, m, r, line); } else { std::mem::swap(&mut node.line, &mut line); Node::insert(&mut node.left, l, m, line); } } } pub struct LiChaoTree { root: Link, left: T, right: T, } impl LiChaoTree { pub fn new(left: T, right: T) -> Self { LiChaoTree { root: None, left: left, right: right, } } pub fn insert(&mut self, a: T, b: T) { Node::insert(&mut self.root, self.left, self.right, Line(a, b)); } pub fn find(&self, x: T) -> T { assert!(self.left <= x && x < self.right); Node::find(&self.root, self.left, self.right, x) } } } use std::io::Read; use std::io::Write; fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let q: usize = it.next().unwrap().parse().unwrap(); let mut cht = lichao::LiChaoTree::new(-1_000_000_000, 1_000_000_000 + 1); for _ in 0..n { let a: i64 = it.next().unwrap().parse().unwrap(); let b: i64 = it.next().unwrap().parse().unwrap(); cht.insert(a, b); } let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for _ in 0..q { let op: u8 = it.next().unwrap().parse().unwrap(); if op == 0 { let a: i64 = it.next().unwrap().parse().unwrap(); let b: i64 = it.next().unwrap().parse().unwrap(); cht.insert(a, b); } else { let x: i64 = it.next().unwrap().parse().unwrap(); let ans = cht.find(x); writeln!(out, "{}", ans).ok(); } } } fn main() { run(); }