結果

問題 No.1625 三角形の質問
ユーザー koba-e964koba-e964
提出日時 2021-11-06 18:37:29
言語 Rust
(1.77.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,824 bytes
コンパイル時間 20,888 ms
コンパイル使用メモリ 374,036 KB
実行使用メモリ 146,048 KB
最終ジャッジ日時 2024-11-07 17:24:53
合計ジャッジ時間 30,482 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,624 KB
testcase_01 AC 131 ms
22,016 KB
testcase_02 AC 1,859 ms
88,576 KB
testcase_03 AC 924 ms
110,080 KB
testcase_04 AC 1,111 ms
75,392 KB
testcase_05 AC 2,633 ms
146,048 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;

#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}

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

fn main() {
    let n: usize = get();
    let q: usize = get();
    let mut st = Dyn2DSegTree::new(1 << 30);
    for _ in 0..n {
        let mut x = [0i64; 6];
        for i in 0..6 {
            x[i] = get();
        }
        let (l, r, a) = parse(x);
        let old = st.query(l..l + 1, r..r + 1);
        st.update(l, r, max(old, a));
    }
    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);
            let old = st.query(l..l + 1, r..r + 1);
            st.update(l, r, max(old, a));
        } else {
            let l: i64 = get();
            let r: i64 = get();
            let ans = st.query(l..r + 1, l..r + 1);
            println!("{}", max(-1, ans));
        }
    }
}
0