結果

問題 No.3313 Matryoshka
コンテスト
ユーザー LyricalMaestro
提出日時 2026-01-30 00:32:45
言語 Rust
(1.92.0 + proconio + num + itertools)
結果
TLE  
実行時間 -
コード長 3,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,476 ms
コンパイル使用メモリ 215,048 KB
実行使用メモリ 52,672 KB
最終ジャッジ日時 2026-01-30 00:33:13
合計ジャッジ時間 12,443 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `L` should have a snake case name
  --> src/main.rs:87:17
   |
87 |         let mut L = self.size + l;
   |                 ^ help: convert the identifier to snake case: `l`
   |
   = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default

warning: variable `R` should have a snake case name
  --> src/main.rs:88:17
   |
88 |         let mut R = self.size + r;
   |                 ^ help: convert the identifier to snake case: `r`

ソースコード

diff #
raw source code 

use proconio::input;

struct SegmentTree {
    size: usize,
    a: Vec<Vec<usize>>,
}

impl SegmentTree {
    fn new(n: usize) -> Self {
        let mut size = 1usize;
        while size < n {
            size <<= 1;
        }
        Self {
            size,
            a: vec![Vec::new(); 2 * size],
        }
    }

    fn set(&mut self, x: usize, j: usize) {
        let mut idx = self.size + x;
        self.a[idx].push(j);

        while idx > 1 {
            idx >>= 1;
            let left = idx << 1;
            let right = left | 1;

            // --- 借用衝突回避のため clone ---
            let left_vec = self.a[left].clone();
            let right_vec = self.a[right].clone();

            let dst = &mut self.a[idx];
            Self::merge(dst, &left_vec, &right_vec);
        }
    }

    fn merge(dst: &mut Vec<usize>, left: &Vec<usize>, right: &Vec<usize>) {
        dst.clear();
        dst.reserve(left.len() + right.len());

        let mut i = 0usize;
        let mut j = 0usize;
        while i < left.len() || j < right.len() {
            if i < left.len() && j < right.len() {
                if left[i] <= right[j] {
                    dst.push(left[i]);
                    i += 1;
                } else {
                    dst.push(right[j]);
                    j += 1;
                }
            } else if i < left.len() {
                dst.push(left[i]);
                i += 1;
            } else {
                dst.push(right[j]);
                j += 1;
            }
        }
    }

    // Python の _calc と等価
    fn calc(array: &Vec<usize>, x: usize) -> usize {
        if array.is_empty() {
            return 0;
        }
        if x <= array[0] {
            return array.len();
        }

        // lower_bound
        let mut lo = 0usize;
        let mut hi = array.len();
        while lo < hi {
            let mid = (lo + hi) / 2;
            if array[mid] < x {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        array.len() - lo
    }

    fn get_sum(&self, l: usize, r: usize, x: usize) -> usize {
        let mut L = self.size + l;
        let mut R = self.size + r;
        let mut res = 0usize;

        while L < R {
            if (R & 1) == 1 {
                R -= 1;
                res += Self::calc(&self.a[R], x);
            }
            if (L & 1) == 1 {
                res += Self::calc(&self.a[L], x);
                L += 1;
            }
            L >>= 1;
            R >>= 1;
        }
        res
    }
}

fn main() {
    input! {
        n: usize,
        lr_in: [(usize, usize); n],
    }

    let mut max_r = 0usize;
    let mut lr: Vec<(usize, usize, usize)> = Vec::with_capacity(n);
    for (i, (l, r)) in lr_in.into_iter().enumerate() {
        max_r = max_r.max(r);
        lr.push((l, r, i));
    }

    // l の降順（Python の reverse=True）
    lr.sort_by(|a, b| b.0.cmp(&a.0));

    let mut seg = SegmentTree::new(max_r + 1);

    let mut ans: i64 = 0;
    for (l, r, idx) in lr {
        ans += seg.get_sum(l, r, idx) as i64;
        seg.set(r, idx);
    }

    println!("{}", ans);
}
0