結果

問題 No.1625 三角形の質問
ユーザー koba-e964koba-e964
提出日時 2021-11-06 18:45:55
言語 Rust
(1.77.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,847 bytes
コンパイル時間 16,091 ms
コンパイル使用メモリ 375,236 KB
実行使用メモリ 101,272 KB
最終ジャッジ日時 2024-11-07 17:32:38
合計ジャッジ時間 79,239 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 153 ms
9,256 KB
testcase_02 AC 1,489 ms
42,360 KB
testcase_03 AC 641 ms
49,060 KB
testcase_04 AC 879 ms
34,200 KB
testcase_05 AC 2,226 ms
69,208 KB
testcase_06 AC 5,858 ms
101,012 KB
testcase_07 AC 5,723 ms
101,012 KB
testcase_08 AC 5,736 ms
100,884 KB
testcase_09 AC 5,299 ms
100,988 KB
testcase_10 AC 5,041 ms
101,272 KB
testcase_11 AC 5,334 ms
101,148 KB
testcase_12 AC 5,500 ms
100,768 KB
testcase_13 AC 5,439 ms
100,880 KB
testcase_14 AC 5,790 ms
101,024 KB
testcase_15 TLE -
testcase_16 AC 304 ms
19,348 KB
testcase_17 AC 303 ms
35,116 KB
testcase_18 AC 330 ms
11,852 KB
testcase_19 AC 384 ms
42,516 KB
権限があれば一括ダウンロードができます

ソースコード

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 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