Submission #10115469


Source Code Expand

Copy
mod lichao {
    use std;
    use std::cmp::Ordering;
    type T = i64;
    const INF: T = std::i64::MAX / 2;
    fn get_mid(l: T, r: T) -> T {
        (l + r) / 2
    }
    fn compare(l: T, r: T) -> Ordering {
        l.cmp(&r)
    }
    #[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() {
                let val = t.line.eval(x);
                if compare(val, ans) == Ordering::Less {
                    ans = val;
                }
                let m = get_mid(l, r);
                node = if x <= m {
                    r = m;
                    &t.left
                } else {
                    l = m + 1;
                    &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 compare(node.line.eval(l), line.eval(l)) == Ordering::Greater {
                std::mem::swap(&mut node.line, &mut line);
            }
            let m = get_mid(l, r);
            if compare(node.line.eval(r - 1), line.eval(r - 1)) != Ordering::Greater {
                return;
            } else if compare(node.line.eval(m), line.eval(m)) == Ordering::Less {
                Node::insert(&mut node.right, m + 1, 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 m = 100_000usize;
    let size = m.next_power_of_two();
    let mut seg: Vec<_> = (0..(2 * size)).map(|_| lichao::LiChaoTree::new(0, 1_000_000 + 1)).collect();
    let mut open = vec![vec![]; size];
    for _ in 0..n {
        let o: usize = it.next().unwrap().parse().unwrap();
        let c: usize = {
            let c: i32 = it.next().unwrap().parse().unwrap();
            if c == -1 {
                size
            } else {
                (c + 1) as usize
            }
        };
        let d: i64 = it.next().unwrap().parse().unwrap();
        let x: i64 = it.next().unwrap().parse().unwrap();
        open[o].push((c, d, x));
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    let mut stack = vec![(1, 0, size)];
    while let Some((k, l, r)) = stack.pop() {
        if k >= size {
            for &(c, d, x) in open[k - size].iter() {
                let mut val = std::i64::MAX / 2;
                let mut q = k - 1;
                while q > 0 {
                    val = std::cmp::min(val, seg[q].find(d));
                    q >>= 1;
                }
                val = std::cmp::min(val + d * d, x);
                writeln!(out, "{}", val).ok();
                let mut l = k;
                let mut r = c + size;
                let (a, b) = (-2 * d, val + d * d);
                while l < r {
                    if l & 1 == 1 {
                        seg[l].insert(a, b);
                        l += 1;
                    }
                    if r & 1 == 1 {
                        r -= 1;
                        seg[r].insert(a, b);
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }
        } else {
            let m = (l + r) / 2;
            stack.push((2 * k + 1, m, r));
            stack.push((2 * k, l, m));
        }
    }
}

fn main() {
    run();
}

Submission Info

Submission Time
Task I - Ramen
User sansen
Language Rust (1.15.1)
Score 300
Code Size 5054 Byte
Status
Exec Time 467 ms
Memory 60532 KB

Test Cases

Set Name Score / Max Score Test Cases
All 300 / 300 0-sample-1, 0-sample-2, 1-random-0, 1-random-1, 1-random-2, 1-random-3, 1-random-4, 2-0, 2-1, 3-0, 3-1, 4-1, 4-2, 5-0, 5-1, 6-0, 6-1, 6-2, 7-1
Case Name Status Exec Time Memory
0-sample-1 7 ms 14588 KB
0-sample-2 7 ms 14588 KB
1-random-0 15 ms 14588 KB
1-random-1 20 ms 14588 KB
1-random-2 19 ms 14588 KB
1-random-3 225 ms 39676 KB
1-random-4 467 ms 60532 KB
2-0 253 ms 46580 KB
2-1 259 ms 48628 KB
3-0 260 ms 46580 KB
3-1 263 ms 46580 KB
4-1 108 ms 32244 KB
4-2 94 ms 29052 KB
5-0 320 ms 38008 KB
5-1 321 ms 38008 KB
6-0 46 ms 25076 KB
6-1 51 ms 23540 KB
6-2 55 ms 23672 KB
7-1 59 ms 32244 KB