結果

問題 No.2304 Distinct Elements
ユーザー akakimidoriakakimidori
提出日時 2023-05-12 22:02:16
言語 Rust
(1.77.0)
結果
AC  
実行時間 35 ms / 3,000 ms
コード長 5,381 bytes
コンパイル時間 4,436 ms
コンパイル使用メモリ 149,712 KB
実行使用メモリ 9,760 KB
最終ジャッジ日時 2023-08-19 04:47:25
合計ジャッジ時間 6,479 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 33 ms
6,660 KB
testcase_05 AC 31 ms
6,620 KB
testcase_06 AC 32 ms
6,692 KB
testcase_07 AC 33 ms
6,624 KB
testcase_08 AC 31 ms
6,624 KB
testcase_09 AC 29 ms
7,600 KB
testcase_10 AC 30 ms
7,616 KB
testcase_11 AC 29 ms
7,652 KB
testcase_12 AC 30 ms
7,664 KB
testcase_13 AC 29 ms
7,716 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 0 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 0 ms
4,380 KB
testcase_19 AC 0 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 0 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 19 ms
6,788 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 16 ms
6,020 KB
testcase_32 AC 23 ms
6,816 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 24 ms
6,828 KB
testcase_35 AC 28 ms
7,296 KB
testcase_36 AC 2 ms
4,376 KB
testcase_37 AC 10 ms
4,376 KB
testcase_38 AC 32 ms
6,308 KB
testcase_39 AC 33 ms
6,680 KB
testcase_40 AC 20 ms
5,036 KB
testcase_41 AC 10 ms
4,380 KB
testcase_42 AC 18 ms
6,148 KB
testcase_43 AC 27 ms
9,760 KB
testcase_44 AC 23 ms
6,748 KB
testcase_45 AC 18 ms
4,992 KB
testcase_46 AC 14 ms
4,512 KB
testcase_47 AC 1 ms
4,376 KB
testcase_48 AC 1 ms
4,376 KB
testcase_49 AC 35 ms
7,704 KB
testcase_50 AC 35 ms
7,648 KB
testcase_51 AC 33 ms
7,644 KB
testcase_52 AC 20 ms
6,688 KB
testcase_53 AC 14 ms
7,712 KB
testcase_54 AC 19 ms
6,680 KB
testcase_55 AC 18 ms
6,180 KB
testcase_56 AC 18 ms
6,180 KB
testcase_57 AC 22 ms
7,700 KB
testcase_58 AC 20 ms
7,664 KB
testcase_59 AC 20 ms
6,684 KB
testcase_60 AC 1 ms
4,380 KB
testcase_61 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut a = a;
    a.sort();
    for (i, a) in a.iter_mut().enumerate() {
        *a -= i as i64;
    }
    let mut slope = slopetrick::SlopeTrick::new();
    for a in a {
        slope.left_min();
        slope.add_abs(a);
    }
    let ans = slope.find_min();
    println!("{}", ans);
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
// ---------- begin slope trick ----------
// reference
// https://maspypy.com/slope-trick-1-%e8%a7%a3%e8%aa%ac%e7%b7%a8
mod slopetrick {

    #[derive(Default, Debug, Clone)]
    struct InternalHeap {
        h: std::collections::BinaryHeap<i64>,
        add: i64,
    }

    impl InternalHeap {
        fn push(&mut self, val: i64) {
            self.h.push(val - self.add);
        }
        fn pop(&mut self) -> Option<i64> {
            self.h.pop().map(|v| v + self.add)
        }
        fn peek(&self) -> Option<i64> {
            self.h.peek().map(|v| v + self.add)
        }
        fn add(&mut self, v: i64) {
            self.add += v;
        }
        fn clear(&mut self) {
            self.h.clear();
            self.add = 0;
        }
        fn len(&self) -> usize {
            self.h.len()
        }
    }

    #[derive(Default, Debug, Clone)]
    pub struct SlopeTrick {
        min_f: i64,
        left: InternalHeap,
        right: InternalHeap,
    }

    #[allow(dead_code)]
    impl SlopeTrick {
        pub fn new() -> Self {
            SlopeTrick::default()
        }
        pub fn find_min(&self) -> i64 {
            self.min_f
        }
        pub fn find_argmin(&self) -> i64 {
            self.left.peek().or(self.right.peek().map(|p| -p)).unwrap_or(0)
        }
        pub fn add_const(&mut self, a: i64) {
            self.min_f += a;
        }
        // max(0, x - a), _/
        pub fn add_x_a(&mut self, mut a: i64) {
            if self.left.peek().map_or(false, |p| a < p) {
                self.min_f += self.left.peek().unwrap() - a;
                self.left.push(a);
                a = self.left.pop().unwrap();
            }
            self.right.push(-a);
        }
        // max(0, a - x), \_
        pub fn add_a_x(&mut self, mut a: i64) {
            if self.right.peek().map_or(false, |p| -p < a) {
                self.min_f += a + self.right.peek().unwrap();
                self.right.push(-a);
                a = -self.right.pop().unwrap();
            }
            self.left.push(a);
        }
        // \/
        pub fn add_abs(&mut self, x: i64) {
            self.add_a_x(x);
            self.add_x_a(x);
        }
        // f(x) = min f(y) (y <= x),
        // \_/ => \_
        pub fn left_min(&mut self) {
            self.right.clear();
        }
        // f(x) = min f(y) (x <= y),
        // \_/ => _/
        pub fn right_min(&mut self) {
            self.left.clear();
        }
        // f(x) => f(x - shift)
        // ex. |x| => |x - shift|
        pub fn shift(&mut self, shift: i64) {
            self.left.add(shift);
            self.right.add(-shift);
        }
        // g(x) = f(y) (x - b <= y <= x - a)
        pub fn slide_min(&mut self, a: i64, b: i64) {
            assert!(a <= b);
            self.left.add(a);
            self.right.add(-b);
        }
        // f := f + g
        // g := 0
        pub fn merge(&mut self, rhs: &mut Self) {
            if self.left.len() + self.right.len() < rhs.left.len() + rhs.right.len() {
                std::mem::swap(self, rhs);
            }
            self.add_const(rhs.min_f);
            for x in rhs.left.h.drain() {
                self.add_a_x(x + rhs.left.add);
            }
            for x in rhs.right.h.drain() {
                self.add_x_a(-x + rhs.right.add);
            }
            rhs.clear();
        }
        pub fn clear(&mut self) {
            self.min_f = 0;
            self.left.clear();
            self.right.clear();
        }
    }
}
// ---------- end slope trick ----------
0