結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー hatoohatoo
提出日時 2017-10-12 17:06:51
言語 Rust
(1.77.0)
結果
AC  
実行時間 71 ms / 1,000 ms
コード長 4,982 bytes
コンパイル時間 2,121 ms
コンパイル使用メモリ 161,796 KB
実行使用メモリ 13,768 KB
最終ジャッジ日時 2023-08-20 09:49:34
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
13,768 KB
testcase_01 AC 49 ms
13,744 KB
testcase_02 AC 5 ms
5,848 KB
testcase_03 AC 4 ms
5,868 KB
testcase_04 AC 5 ms
5,904 KB
testcase_05 AC 5 ms
5,924 KB
testcase_06 AC 4 ms
5,876 KB
testcase_07 AC 5 ms
5,884 KB
testcase_08 AC 5 ms
5,856 KB
testcase_09 AC 6 ms
5,888 KB
testcase_10 AC 5 ms
5,816 KB
testcase_11 AC 5 ms
5,932 KB
testcase_12 AC 49 ms
13,600 KB
testcase_13 AC 62 ms
13,696 KB
testcase_14 AC 60 ms
13,592 KB
testcase_15 AC 71 ms
13,552 KB
testcase_16 AC 55 ms
13,252 KB
testcase_17 AC 48 ms
13,276 KB
testcase_18 AC 60 ms
13,232 KB
testcase_19 AC 58 ms
13,576 KB
testcase_20 AC 48 ms
13,604 KB
testcase_21 AC 63 ms
13,280 KB
testcase_22 AC 51 ms
13,672 KB
testcase_23 AC 5 ms
5,912 KB
testcase_24 AC 4 ms
5,848 KB
testcase_25 AC 5 ms
5,908 KB
権限があれば一括ダウンロードができます

ソースコード

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