結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー hatoo
提出日時 2017-10-12 17:06:51
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 52 ms / 1,000 ms
コード長 4,982 bytes
コンパイル時間 13,921 ms
コンパイル使用メモリ 378,500 KB
実行使用メモリ 13,808 KB
最終ジャッジ日時 2024-11-30 11:14:26
合計ジャッジ時間 15,773 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BTreeSet};

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn get<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn get2<T: FromStr, U: FromStr>() -> (T, U)
    where
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }

    #[allow(dead_code)]
    pub fn get3<S: FromStr, T: FromStr, U: FromStr>() -> (S, T, U)
    where
        <S as FromStr>::Err: Debug,
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }
}


#[allow(unused_macros)]
macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    }
}

#[derive(Clone)]
struct BIT<T: Clone> {
    buf: Vec<T>,
    zero: T,
}

impl<T: Clone + Ord + std::ops::Add<T, Output = T>> BIT<T> {
    fn new(n: usize, zero: &T) -> BIT<T> {
        BIT {
            buf: vec![zero.clone(); n + 1],
            zero: zero.clone(),
        }
    }
    fn sum(&self, i: usize) -> T {
        let mut i = i;
        let mut s = self.zero.clone();
        while i > 0 {
            s = s + self.buf[i].clone();
            i = i & (i - 1);
        }
        s
    }

    fn add(&mut self, i: usize, x: &T) {
        let mut i = i as i64;
        while i < self.buf.len() as i64 {
            let y = {
                let t = self.buf[i as usize].clone();
                t + x.clone()
            };
            self.buf[i as usize] = y;
            i += i & -i;
        }
    }

    fn bin_search(&self, x: &T, low: usize, high: usize) -> usize {
        let mid = (low + high) / 2;
        if mid == low {
            return high;
        }

        match self.sum(mid).cmp(x) {
            Ordering::Less => self.bin_search(x, mid, high),
            Ordering::Equal => self.bin_search(x, low, mid),
            Ordering::Greater => self.bin_search(x, low, mid),
        }
    }
}



fn main() {
    let (n, m): (usize, usize) = util::get2();
    let inf = 100010;
    let xab: Vec<(usize, usize, usize)> = (0..n)
        .map(|_| {
            let (x, a, b): (usize, usize, usize) = util::get3();
            (x, 100001 - a, 100001 - b)
        })
        .collect();

    let mut below_3 = vec![BIT::new(inf + 10, &0i64); 3];
    let mut three = xab.iter().filter(|t| t.0 >= 3).count();

    let av: BTreeSet<usize> = xab.iter().map(|t| t.1).collect();
    let mut a_map = vec![Vec::new(); inf + 1];

    let mut ans = inf;

    for &(x, a, b) in &xab {
        if x < 3 {
            below_3[x].add(b, &1);
            a_map[a].push((x, b));
        }
    }

    // SA == inf
    {
        let two = three + below_3[2].sum(inf) as usize;

        if m > two {
            let rest = m - two;
            let sb = below_3[1].bin_search(&(rest as i64), 0, inf);
            if sb != inf {
                ans = min(ans, three + below_3[2].sum(sb) as usize);
            }
        } else {
            ans = min(ans, three);
        }
    }


    for &a in &av {
        for &(x, b) in &a_map[a] {
            below_3[x].add(b, &-1);
            if x == 2 {
                three += 1;
            } else {
                below_3[x + 1].add(b, &1);
            }
        }
        let two = three + below_3[2].sum(inf) as usize;

        if m > two {
            let rest = m - two;
            let sb = below_3[1].bin_search(&(rest as i64), 0, inf);
            if sb != inf {
                ans = min(ans, three + below_3[2].sum(sb) as usize);
            }
        } else {
            ans = min(ans, three);
            break;
        }
    }

    println!("{}", ans);

}
0