結果

問題 No.2304 Distinct Elements
コンテスト
ユーザー akakimidori
提出日時 2023-05-12 22:02:16
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 31 ms / 3,000 ms
コード長 5,381 bytes
コンパイル時間 16,961 ms
コンパイル使用メモリ 380,128 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2025-01-08 22:29:26
合計ジャッジ時間 20,682 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

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