結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー hatoohatoo
提出日時 2017-10-12 16:28:18
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 5,013 bytes
コンパイル時間 13,516 ms
コンパイル使用メモリ 385,460 KB
実行使用メモリ 13,684 KB
最終ジャッジ日時 2024-04-28 17:04:45
合計ジャッジ時間 15,709 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
13,676 KB
testcase_01 AC 59 ms
13,684 KB
testcase_02 AC 4 ms
5,888 KB
testcase_03 AC 3 ms
6,016 KB
testcase_04 AC 4 ms
5,888 KB
testcase_05 AC 4 ms
5,760 KB
testcase_06 AC 5 ms
5,888 KB
testcase_07 AC 5 ms
5,888 KB
testcase_08 WA -
testcase_09 AC 4 ms
5,760 KB
testcase_10 AC 4 ms
5,888 KB
testcase_11 AC 5 ms
6,016 KB
testcase_12 AC 57 ms
13,568 KB
testcase_13 AC 62 ms
13,612 KB
testcase_14 AC 62 ms
13,548 KB
testcase_15 WA -
testcase_16 AC 59 ms
13,468 KB
testcase_17 AC 56 ms
13,356 KB
testcase_18 AC 61 ms
13,332 KB
testcase_19 AC 59 ms
13,432 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 55 ms
13,680 KB
testcase_23 AC 5 ms
5,888 KB
testcase_24 AC 4 ms
5,888 KB
testcase_25 AC 4 ms
5,888 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, F: Clone + Fn(&T, &T) -> T> {
    buf: Vec<T>,
    f: F,
    zero: T,
}

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

    fn add(&mut self, i: usize, x: &T) {
        // 0 indexed
        let mut i = i as i64 + 1;
        while i < self.buf.len() as i64 {
            let y = {
                let t = &self.buf[i as usize];
                (self.f)(t, x)
            };
            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 => mid,
            Ordering::Greater => self.bin_search(x, low, mid),
        }
    }
}

fn add(x: &i64, y: &i64) -> i64 {
    *x + *y
}


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, add); 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);
            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);
            ans = min(ans, three + below_3[2].sum(sb) as usize);
        } else {
            ans = min(ans, three);
        }
    }

    println!("{}", ans);

}
0