結果

問題 No.1625 三角形の質問
ユーザー koba-e964koba-e964
提出日時 2021-11-06 18:48:07
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 5,953 ms / 6,000 ms
コード長 6,759 bytes
コンパイル時間 14,341 ms
コンパイル使用メモリ 375,324 KB
実行使用メモリ 101,272 KB
最終ジャッジ日時 2024-11-07 17:35:29
合計ジャッジ時間 82,737 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 159 ms
9,388 KB
testcase_02 AC 1,658 ms
42,360 KB
testcase_03 AC 689 ms
49,060 KB
testcase_04 AC 903 ms
34,328 KB
testcase_05 AC 2,199 ms
69,164 KB
testcase_06 AC 5,867 ms
100,888 KB
testcase_07 AC 5,953 ms
101,012 KB
testcase_08 AC 5,903 ms
100,884 KB
testcase_09 AC 5,844 ms
101,032 KB
testcase_10 AC 5,890 ms
101,272 KB
testcase_11 AC 5,794 ms
101,024 KB
testcase_12 AC 5,842 ms
100,768 KB
testcase_13 AC 5,470 ms
101,008 KB
testcase_14 AC 5,946 ms
101,148 KB
testcase_15 AC 5,511 ms
101,028 KB
testcase_16 AC 298 ms
19,348 KB
testcase_17 AC 303 ms
34,992 KB
testcase_18 AC 330 ms
11,848 KB
testcase_19 AC 384 ms
42,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::cmp::*;
use std::io::Read;

fn get_word() -> String {
    let stdin = std::io::stdin();
    let mut stdin=stdin.lock();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

const INF: i64 = 1 << 50;

// (max, -inf)
struct Dyn2DSegTree {
    n: i64,
    root: Node,
    e: i64,
}

struct Node {
    val: i64,
    l: Option<Box<Node>>,
    r: Option<Box<Node>>,
}

impl Dyn2DSegTree {
    fn new(n: i64) -> Self {
        assert_eq!(n & -n, n);
        Dyn2DSegTree {
            n: n,
            root: Node::new(-INF),
            e: -INF,
        }
    }
    // O(log^2 n)
    fn query(&self, x: std::ops::Range<i64>, y: std::ops::Range<i64>) -> i64 {
        self.query_sub(Some(&self.root), x.start, x.end, 0, self.n, y.start, y.end, 0, self.n)
    }
    fn query_sub(&self, node: Option<&Node>,
                 lx: i64, rx: i64, ax: i64, bx: i64,
                 ly: i64, ry: i64, ay: i64, by: i64) -> i64 {
        let node = if let Some(node) = node {
            node
        } else {
            return self.e;
        };
        if rx <= ax || bx <= lx || ry <= ay || by <= ly {
            return self.e;
        }
        if lx <= ax && bx <= rx && ly <= ay && by <= ry {
            return node.val;
        }
        if bx - ax >= by - ay {
            // bisect on x
            assert!(bx - ax >= 2);
            let mid = (bx + ax) / 2;
            let p = self.query_sub(node.l.as_deref(), lx, rx, ax, mid, ly, ry, ay, by);
            let q = self.query_sub(node.r.as_deref(), lx, rx, mid, bx, ly, ry, ay, by);
            return std::cmp::max(p, q);
        }
        // bisect on y
        assert!(by - ay >= 2);
        let mid = (by + ay) / 2;
        let p = self.query_sub(node.l.as_deref(), lx, rx, ax, bx, ly, ry, ay, mid);
        let q = self.query_sub(node.r.as_deref(), lx, rx, ax, bx, ly, ry, mid, by);
        std::cmp::max(p, q)
    }
    fn update(&mut self, x: i64, y: i64, val: i64) {
        let n = self.n;
        Self::update_sub(&mut self.root, x, y, val, self.e, 0, n, 0, n);
    }
    fn update_sub(node: &mut Node, x: i64, y: i64, val: i64, e: i64,
                  ax: i64, bx: i64, ay: i64, by: i64) {
        if x < ax || bx <= x || y < ay || by <= y {
            unreachable!();
        }
        if (ax, bx) == (x, x + 1) && (ay, by) == (y, y + 1) {
            node.val = val;
            return;
        }
        if bx - ax >= by - ay {
            // bisect on x
            assert!(bx - ax >= 2);
            let mid = (bx + ax) / 2;
            if x >= mid {
                if node.r.is_none() {
                    node.r = Some(Box::new(Node::new(e)));
                }
                Self::update_sub(node.r.as_mut().unwrap(), x, y, val, e,
                                 mid, bx, ay, by);
            } else {
                if node.l.is_none() {
                    node.l = Some(Box::new(Node::new(e)));
                }
                Self::update_sub(node.l.as_mut().unwrap(), x, y, val, e,
                                 ax, mid, ay, by);
            }
        } else {
            // bisect on y
            assert!(by - ay >= 2);
            let mid = (by + ay) / 2;
            if y >= mid {
                if node.r.is_none() {
                    node.r = Some(Box::new(Node::new(e)));
                }
                Self::update_sub(node.r.as_mut().unwrap(), x, y, val, e,
                                 ax, bx, mid, by);
            } else {
                if node.l.is_none() {
                    node.l = Some(Box::new(Node::new(e)));
                }
                Self::update_sub(node.l.as_mut().unwrap(), x, y, val, e,
                                 ax, bx, ay, mid);
            }
        }
        let p = node.l.as_ref().map(|v| v.val).unwrap_or(e);
        let q = node.r.as_ref().map(|v| v.val).unwrap_or(e);
        node.val = std::cmp::max(p, q);
    }
}

impl Node {
    fn new(e: i64) -> Self {
        Node {
            val: e,
            l: None,
            r: None,
        }
    }
}

fn parse(x: [i64; 6]) -> (i64, i64, i64) {
    let l = min(min(x[0], x[2]), x[4]);
    let r = max(max(x[0], x[2]), x[4]);
    let a = x[2] - x[0];
    let b = x[3] - x[1];
    let c = x[4] - x[0];
    let d = x[5] - x[1];
    (l, r, (a * d - b * c).abs())
}

// The author read the editorial before implementing this.
// Tags: 2d-segment-trees, dynamic-segment-trees, coordinate-compression
fn main() {
    let n: usize = get();
    let q: usize = get();
    let mut coo = vec![];
    let mut orig = vec![];
    for _ in 0..n {
        let mut x = [0i64; 6];
        for i in 0..6 {
            x[i] = get();
        }
        let (l, r, a) = parse(x);
        coo.push(l);
        coo.push(r);
        orig.push((l, r, a));
    }
    let mut qs = vec![];
    for _ in 0..q {
        let ty: i32 = get();
        if ty == 1 {
            let mut x = [0i64; 6];
            for i in 0..6 {
                x[i] = get();
            }
            let (l, r, a) = parse(x);
            coo.push(l);
            coo.push(r);
            qs.push(Err((l, r, a)));
        } else {
            let l: i64 = get();
            let r: i64 = get();
            coo.push(l);
            coo.push(r + 1);
            qs.push(Ok((l, r + 1)));
        }
    }
    coo.sort(); coo.dedup();
    let m = coo.len();
    let mut sz = 1;
    while m > sz {
        sz *= 2;
    }
    let mut st = Dyn2DSegTree::new(sz as i64);
    for (l, r, a) in orig {
        let l = coo.binary_search(&l).unwrap() as i64;
        let r = coo.binary_search(&r).unwrap() as i64;
        let old = st.query(l..l + 1, r..r + 1);
        if old < a {
            st.update(l, r, a);
        }
    }
    for q in qs {
        match q {
            Err((l, r, a)) => {
                let l = coo.binary_search(&l).unwrap() as i64;
                let r = coo.binary_search(&r).unwrap() as i64;
                let old = st.query(l..l + 1, r..r + 1);
                if old < a {
                    st.update(l, r, a);
                }
            }
            Ok((l, r)) => {
                let l = coo.binary_search(&l).unwrap() as i64;
                let r = coo.binary_search(&r).unwrap() as i64;
                println!("{}", max(st.query(l..r, l..r), -1));
            }
        }
    }
}
0