Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3689

Problem Lang User Status Time Memory
Segment Add Get Min rust sansen AC 1514 ms 470.45 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.59 MiB
example_01 AC 5 ms 0.64 MiB
max_random_00 AC 1514 ms 469.61 MiB
max_random_01 AC 1509 ms 470.45 MiB
max_random_02 AC 1504 ms 469.75 MiB
random_00 AC 1008 ms 332.90 MiB
random_01 AC 1142 ms 365.66 MiB
random_02 AC 592 ms 200.65 MiB
small_00 AC 7 ms 0.55 MiB
small_01 AC 7 ms 0.60 MiB

mod lichao { use std; type T = i64; fn get_mid(l: T, r: T) -> T { (l + r) / 2 } #[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: Option<Line>, left: Link, right: Link, } impl Node { fn find(node: &Link, left: T, right: T, x: T) -> Option<T> { let mut node = node; let mut ans = None; let mut l = left; let mut r = right; while let Some(t) = node.as_ref() { if let Some(line) = t.line { let val = line.eval(x); if let Some(u) = ans { if val < u { ans = Some(val); } } else { ans = Some(val) } } let m = get_mid(l, r); node = if x < m { r = m; &t.left } else { l = m; &t.right }; } ans } fn insert(node: &mut Link, l: T, r: T, x: T, y: T, mut line: Line) { if r <= x || y <= l { return; } if node.is_none() { *node = Some(Box::new(Node { line: None, left: None, right: None, })); } let node = node.as_mut().unwrap(); if x <= l && r <= y { if node.line.is_none() { node.line = Some(line); return; } if node.line.unwrap().eval(l) > line.eval(l) { std::mem::swap(node.line.as_mut().unwrap(), &mut line); } let m = get_mid(l, r); if node.line.unwrap().eval(r) <= line.eval(r) { return; } else if node.line.unwrap().eval(m) < line.eval(m) { Node::insert(&mut node.right, m, r, x, y, line); } else { std::mem::swap(node.line.as_mut().unwrap(), &mut line); Node::insert(&mut node.left, l, m, x, y, line); } } else { let m = get_mid(l, r); Node::insert(&mut node.left, l, m, x, y, line); Node::insert(&mut node.right, m, r, x, y, 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, l: T, r: T) { Node::insert(&mut self.root, self.left, self.right, l, r, Line(a, b)); } pub fn find(&self, x: T) -> Option<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, 1_000_000_000 + 1); for _ in 0..n { let l: i64 = it.next().unwrap().parse().unwrap(); let r: i64 = it.next().unwrap().parse().unwrap(); let a: i64 = it.next().unwrap().parse().unwrap(); let b: i64 = it.next().unwrap().parse().unwrap(); cht.insert(a, b, l, r); } 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 l: i64 = it.next().unwrap().parse().unwrap(); let r: i64 = it.next().unwrap().parse().unwrap(); let a: i64 = it.next().unwrap().parse().unwrap(); let b: i64 = it.next().unwrap().parse().unwrap(); cht.insert(a, b, l, r); } else { let x: i64 = it.next().unwrap().parse().unwrap(); if let Some(ans) = cht.find(x) { writeln!(out, "{}", ans).ok(); } else { writeln!(out, "INFINITY").ok(); } } } } fn main() { run(); }