結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー QiToY
提出日時 2025-10-05 16:24:03
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,960 bytes
コンパイル時間 12,584 ms
コンパイル使用メモリ 398,200 KB
実行使用メモリ 123,488 KB
最終ジャッジ日時 2025-10-05 16:24:30
合計ジャッジ時間 25,134 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused_imports)]

fn main() {
    input! {
        n: usize, k: usize, d: i64,
        h: [i64; n],
    }
    let mut seg = vec![vec![]; 4 * n];
    let mut seg2 = vec![vec![]; 4 * n];
    for (i, h) in h.into_iter().flat_map(|h| [h, h - d]).enumerate() {
        seg[i + 2 * n].push(h);
    }
    for i in (0..2 * n).rev() {
        let mut v = seg[i << 1].clone();
        seg[i].append(&mut v);
        let mut v = seg[i << 1 | 1].clone();
        seg[i].append(&mut v);
        seg[i].sort();
    }
    for i in 0..4 * n {
        let mut c = 0;
        seg2[i].push(c);
        for &a in &seg[i] {
            c += a;
            seg2[i].push(c);
        }
    }
    let mut ans = i64::MAX;
    for i in k..=n {
        let (mut ok, mut ng) = (1i64 << 30, -1 << 30);
        while ok.abs_diff(ng) > 1 {
            let mid = (ok + ng) / 2;
            let (mut l, mut r) = (2 * (i - k + n), 2 * (i + n));
            let mut cnt = 0;
            while l < r {
                if l & 1 == 1 {
                    cnt += seg[l].partition_point(|&s| s < mid);
                    l += 1;
                }
                if r & 1 == 1 {
                    r -= 1;
                    cnt += seg[r].partition_point(|&s| s < mid);
                }
                l >>= 1;
                r >>= 1;
            }
            *if cnt < k { &mut ng } else { &mut ok } = mid;
        }
        let mut sum = 0;
        let (mut l, mut r) = (2 * i - 2 * k + 2 * n, 2 * i + 2 * n);
        while l < r {
            if l & 1 == 1 {
                let i = seg[l].partition_point(|&s| s < ok);
                sum += i as i64 * ok - seg2[l][i];
                sum += (seg2[l].last().unwrap() - seg2[l][i]) - (seg[l].len() - i) as i64 * ok;
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                let i = seg[r].partition_point(|&s| s < ok);
                sum += i as i64 * ok - seg2[r][i];
                sum += (seg2[r].last().unwrap() - seg2[r][i]) - (seg[r].len() - i) as i64 * ok;
            }
            l >>= 1;
            r >>= 1;
        }
        chmin!(ans, sum / 2 - d * 2);
    }
    println!("{ans}");
}

/*
a[i..i+k]
b..=b+d
cost = sum (|a - b| + |a - (b+d)|)/2
= sum (|a - b| + |(a-d) - b|)/2
*/

use proconio::{input, marker::*};
use std::{cmp::Reverse, collections::*};

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a < tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a > tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
/// mvec![]
macro_rules! mvec {
    ($val:expr; ()) => {
        $val
    };
    ($val:expr; ($size:expr $(,$rest:expr)*)) => {
        vec![mvec![$val; ($($rest),*)]; $size]
    };
}
0