結果

問題 No.3313 Matryoshka
コンテスト
ユーザー koba-e964
提出日時 2025-10-26 15:58:46
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 4,759 bytes
コンパイル時間 10,392 ms
コンパイル使用メモリ 399,252 KB
実行使用メモリ 111,344 KB
最終ジャッジ日時 2025-10-26 15:59:05
合計ジャッジ時間 17,593 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).unwrap();
    ret
}


// (+, 0)
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(0),
            e: 0,
        }
    }
    // 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 p + q; // op
        }
        // 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);
        p + q // op
    }
    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 = p + q; // op
    }
}

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

// https://yukicoder.me/problems/no/3313 (3)
// 区間の交差 + クエリー問題
// -> WA。i < j という条件を見落としていた。これがあると動的セグメント木が必要になるはず。
// Tags: dynamic-segment-trees, dynamic-2d-segment-trees
fn main() {
    let n = getline().trim().parse::<usize>().unwrap();
    let mut lr = vec![];
    for _ in 0..n {
        let ints = getline().trim().split_whitespace()
            .map(|x| x.parse::<usize>().unwrap())
            .collect::<Vec<_>>();
        lr.push((ints[0], ints[1]));
    }
    const W: usize = 1 << 20;
    let mut st = Dyn2DSegTree::new(W as i64);
    let mut ans = 0i64;
    for i in 0..n {
        let (l, r) = lr[i];
        let l = l as i64;
        let r = r as i64;
        ans += st.query(0..l, r..W as i64);
        st.update(l, r, 1);
    }
    println!("{ans}");
}
0