結果

問題 No.3085 Easy Problems
コンテスト
ユーザー LyricalMaestro
提出日時 2025-07-15 01:32:11
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 614 ms / 2,000 ms
コード長 2,632 bytes
コンパイル時間 26,122 ms
コンパイル使用メモリ 398,992 KB
実行使用メモリ 43,924 KB
最終ジャッジ日時 2025-07-15 10:15:52
合計ジャッジ時間 38,774 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/problems/no/3085

use std::collections::{HashMap, HashSet};

use proconio::input;

pub struct BinaryIndexTree {
    size: usize,
    array: Vec<u64>
}

impl BinaryIndexTree {

    pub fn new(size: usize) -> Self {
        Self {
            size,
            array: vec![0; size + 1]
        }
    }

    pub fn add(&mut self, index: usize, value: u64) {
        let mut ind = index as i64;
        while ind <= self.size as i64 {
            self.array[ind as usize] += value;
            ind += ind & (-ind);
        }
    }

    pub fn sum(&mut self, index: usize) -> u64 {
        let mut ind = index as i64;
        let mut answer = 0;
        while ind > 0 {
            answer += self.array[ind as usize] ;
            ind -= ind & (-ind);
        }
        answer
    }
}

fn main() {
    input! {
        n: usize,
        ab: [(u64, u64); n],
        q: usize,
        xy: [(u64, u64); q]
    }

    //  bのmap
    let mut b_map: HashMap<u64, Vec<u64>> = HashMap::new();
    for (a, b) in ab.iter() {
        if !b_map.contains_key(b) {
            b_map.insert(*b, vec![]);
        }
        b_map.get_mut(b).unwrap().push(*a);
    }
    for entry in b_map.iter_mut() {
        entry.1.sort();
    }

    //  座標圧縮
    let mut a_set = ab.iter().map(|v| v.0).collect::<HashSet<_>>();
    for (x, _) in xy.iter() {
        a_set.insert(*x);
    }
    let mut a_list = a_set.into_iter().collect::<Vec<_>>();
    a_list.sort();
    let mut a_map = HashMap::new();
    for i in 0..a_list.len() {
        a_map.insert(a_list[i], i + 1);
    }
    let a_max = a_list.len();

    let mut bit = BinaryIndexTree::new(a_max);
    for (a, _) in ab.iter() {
        bit.add(*a_map.get(a).unwrap() as usize, 1);
    }

    //  Kさん
    for (x, y) in xy.iter(){
        let total = bit.sum(*a_map.get(x).unwrap());

        let xx = b_map.get(y);
        if let Some(xx) = xx {
            if *x < xx[0] {
                println!("{}", total);
            } else {
                let mut low = 0;
                let mut high = xx.len() - 1;
                while high - low > 1 {
                    let mid = (high + low) / 2;
                    if xx[mid] <= *x {
                        low = mid;
                    } else {
                        high =  mid;
                    }
                }
                let d = if xx[high] <= *x {
                    high + 1
                } else {
                    low + 1
                };
                println!("{}", total - d as u64);        
            }

        } else {
            println!("{}", total);
        }
    }


}
0