結果

問題 No.3313 Matryoshka
コンテスト
ユーザー koba-e964
提出日時 2025-10-27 10:03:11
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,461 bytes
コンパイル時間 12,236 ms
コンパイル使用メモリ 399,216 KB
実行使用メモリ 447,060 KB
最終ジャッジ日時 2025-10-27 10:03:32
合計ジャッジ時間 20,726 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
}

struct BIT2D {
    n: i32,
    m: i32,
    dat: std::collections::HashMap<(i32, i32), i64>,
}

impl BIT2D {
    pub fn new(n: i32, m: i32) -> Self {
        BIT2D {
            n: n,
            m: m,
            dat: std::collections::HashMap::with_capacity((n + m) as usize),
        }
    }
    pub fn add(&mut self, x: i32, y: i32, val: i64) {
        let mut x = x;
        while x <= self.n {
            let mut y = y;
            while y <= self.m {
                *self.dat.entry((x, y)).or_insert(0) += val;
                y += y & -y;
            }
            x += x & -x;
        }
    }
    pub fn sum(&self, mut xl: i32, mut xr: i32, y: i32) -> i64 {
        let mut sum = 0;
        let get = |x: i32| -> i64 {
            let mut y = y;
            let mut sum = 0;
            while y > 0 {
                sum += self.dat.get(&(x, y)).unwrap_or(&0);
                y -= y & -y;
            }
            sum
        };
        while xr != xl {
            if xr > xl {
                sum += get(xr);
                xr -= xr & -xr;
            } else {
                sum -= get(xl);
                xl -= xl & -xl;
            }
        }
        sum
    }
}

// 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![];
    let mut ls = vec![];
    let mut rs = 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]));
        ls.push(ints[0]);
        rs.push(ints[1]);
    }
    ls.sort(); ls.dedup();
    rs.sort(); rs.dedup();
    const W: i32 = 1 << 19;
    let mut bit = BIT2D::new(W, W);
    let mut ans = 0i64;
    for i in 0..n {
        if i % 1000 == 0 {
            eprintln!("trial {i} out of {n}");
        }
        let (l, r) = lr[i];
        let l = ls.binary_search(&l).unwrap() as i32;
        let r = rs.binary_search(&r).unwrap() as i32;
        ans += bit.sum(r + 1, W, l + 1);
        bit.add(r + 1, l + 1, 1);
    }
    println!("{ans}");
}
0