結果

問題 No.738 平らな農地
ユーザー CoCo_Japan_pan
提出日時 2024-10-01 22:23:05
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 16,005 bytes
コンパイル時間 21,256 ms
コンパイル使用メモリ 395,972 KB
実行使用メモリ 26,644 KB
最終ジャッジ日時 2024-10-01 22:23:36
合計ジャッジ時間 25,497 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// verification-helper: PROBLEM https://yukicoder.me/problems/no/738
pub use __cargo_equip::prelude::*;
use proconio::{fastout, input};
use wavelet_matrix::WaveletMatrix;
use wavelet_matrix_rect_sum::WaveletMatrixRectSum;
#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        a: [i64; n],
    }
    let sorted = {
        let mut ret = a.clone();
        ret.sort();
        ret.dedup();
        ret
    };
    let compressed: Vec<usize> = a.iter().map(|x| sorted.binary_search(x).unwrap()).collect();
    let wm = WaveletMatrix::new(&compressed);
    let wm_sum = WaveletMatrixRectSum::new(&compressed, &a);
    let mid = k / 2;
    let mut ans = i64::MAX;
    for start in 0..=n - k {
        let end = start + k;
        let medium = wm.quantile(start..end, mid);
        let (less, _, more) = wm.rank_less_eq_more(medium, start..end);
        let less_sum = wm_sum.rect_sum(start..end, ..medium);
        let less_diff = less as i64 * sorted[medium] - less_sum;
        let more_sum = wm_sum.rect_sum(start..end, medium + 1..);
        let more_diff = more_sum - more as i64 * sorted[medium];
        ans = ans.min(less_diff + more_diff);
    }
    println!("{}", ans);
}
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
/// 
///  - `bitvec 0.1.0 (path+███████████████████████████████████████████████████████████)`                                   published in ssh
    ://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitvec_0_1_0`
///  - `internal_bits 0.1.0 (path+████████████████████████████████████████████████████████████████████)`                   published in **missing**   
                                            licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_bits_0_1_0`
///  - `internal_type_traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)`     published in **missing**   
                                            licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `wavelet_matrix 0.1.0 (path+███████████████████████████████████████████████████████████████████)`                   published in ssh
    ://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix`
///  - `wavelet_matrix_rect_sum 0.1.0 (path+████████████████████████████████████████████████████████████████████████████)` published in ssh
    ://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix_rect_sum`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __bitvec_0_1_0 {#[derive(Debug,Clone,Copy)]struct Block{block:u64,cum_sum_popcnt:u32,}#[derive(Debug,Clone)]pub struct BitVec{len
            :usize,blocks:Vec<Block>,all_popcnt:usize,one_select:Vec<u32>,zero_select:Vec<u32>,}impl From<&[bool]>for BitVec{fn from(bitvec:&[bool]
            )->Self{let len=bitvec.len();let mut ret=Self::new(len);for(i,&b)in bitvec.iter().enumerate(){if b{ret.set(i);}}ret.build();ret}}impl 
            BitVec{pub fn new(len:usize)->Self{Self{len,blocks:vec![Block{block:0,cum_sum_popcnt:0};(len>>6)+1],all_popcnt:0,one_select:Vec::new
            (),zero_select:Vec::new(),}}pub fn rank1_all(&self)->usize{self.all_popcnt}pub fn rank0_all(&self)->usize{self.len-self.all_popcnt}pub fn 
            access(&self,i:usize)->bool{debug_assert!(i<self.len);(self.blocks[i>>6].block>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i
            <self.len);self.blocks[i>>6].block|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.block.count_ones()).sum
            ::<u32>()as usize;let mut popcnt=0;let one_num=(all_popcnt>>6)+1;let zero_num=((self.len-all_popcnt)>>6)+1;let mut one_select=Vec
            ::with_capacity(one_num);let mut zero_select=Vec::with_capacity(zero_num);for(i,b)in self.blocks.iter_mut().enumerate(){if popcnt as usize
            >=one_select.len()<<6{one_select.push(i as u32);}if(i<<6)-popcnt as usize>=zero_select.len()<<6{zero_select.push(i as u32);}b
            .cum_sum_popcnt=popcnt;popcnt+=b.block.count_ones();}assert_eq!(popcnt as usize,all_popcnt);self.all_popcnt=all_popcnt;self.one_select
            =one_select;self.zero_select=zero_select;}pub fn rank_1(&self,i:usize)->usize{debug_assert!(i<=self.len);let Block{block,cum_sum_popcnt,}
            =self.blocks[i>>6];let mask=(1<<(i&63))-1;let popcnt=(block&mask).count_ones();(cum_sum_popcnt+popcnt)as usize}pub fn rank_0(&self,i:usize
            )->usize{i-self.rank_1(i)}pub fn select_1(&self,i:usize)->Option<usize>{if i>=self.all_popcnt{return None;}let mut ok=if let Some(&ok
            )=self.one_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self
            .one_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};let i=i as u32;while ng-ok>1{let mid=(ok+ng)>>1;if self.blocks[mid]
            .cum_sum_popcnt<=i{ok=mid;}else{ng=mid;}}let rem=i-self.blocks[ok].cum_sum_popcnt;let offset=select1_u64(self.blocks[ok].block,rem as 
            usize);Some((ok<<6)+offset as usize)}pub fn select_0(&self,i:usize)->Option<usize>{let all_0=self.len-self.all_popcnt;if i>=all_0{return 
            None;}let mut ok=if let Some(&ok)=self.zero_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let 
            mut ng=if let Some(&ng)=self.zero_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};while ng-ok>1{let mid=(ok+ng)>>1;if((mid<<6
            )-self.blocks[mid].cum_sum_popcnt as usize)<=i{ok=mid;}else{ng=mid;}}let rem=i-((ok<<6)-self.blocks[ok].cum_sum_popcnt as usize);let 
            offset=select1_u64(!self.blocks[ok].block,rem);Some((ok<<6)+offset as usize)}}#[cfg(target_arch="x86_64")]fn select1_u64(x:u64,index:usize
            )->u32{use std::arch::x86_64::_pdep_u64;let z=1<<index;let y=unsafe{_pdep_u64(z,x)};y.trailing_zeros()}#[cfg(not(target_arch="x86_64"))]fn 
            select1_u64(x:u64,index:usize)->u32{let mut left=0;let mut right=64;while right-left>1{let mid=(left+right)>>1;if(x&((1<<mid)-1
            )).count_ones()>index as u32{right=mid;}else{left=mid;}}left}}
        pub mod __internal_bits_0_1_0 {pub fn ceil_log2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}
        pub mod __internal_type_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add
            <Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove+Display+Debug{}pub trait Zero{fn zero()->Self
            ;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self
            ;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl 
            BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl 
            Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod wavelet_matrix {use crate::__cargo_equip::preludes::wavelet_matrix::*;use bitvec::BitVec;use internal_bits::ceil_log2;use std::ops
            ::RangeBounds;#[derive(Debug,Clone)]pub struct WaveletMatrix{max:usize,len:usize,indices:Vec<BitVec>,sorted_positions:Vec<Option<usize
            >>,counts:Vec<usize>,}impl WaveletMatrix{pub fn new(compressed_list:&[usize])->Self{let len=compressed_list.len();let max=*compressed_list
            .iter().max().unwrap_or(&0);let log=ceil_log2(max as u32+1)as usize;let mut indices=vec![BitVec::new(len);log];let mut tmp=vec![Vec
            ::with_capacity(len);2];let mut list=compressed_list.to_vec();for(ln,index)in indices.iter_mut().enumerate().rev(){for(i,&x)in list.iter
            ().enumerate(){if(x>>ln)&1==1{index.set(i);tmp[1].push(x);}else{tmp[0].push(x);}}index.build();list.clear();list.append(&mut tmp[0]);list
            .append(&mut tmp[1]);}let mut sorted_positions=vec![None;max+1];let mut counts=vec![0;max+1];for(i,&x)in list.iter().enumerate(){if 
            sorted_positions[x].is_none(){sorted_positions[x]=Some(i);}counts[x]+=1;}Self{max,len,indices,sorted_positions,counts,}}pub fn access
            (&self,mut pos:usize)->usize{assert!(pos<self.len);let mut ret=0;for(ln,index)in self.indices.iter().enumerate().rev(){let bit=index
            .access(pos);if bit{ret|=1<<ln;pos=index.rank0_all()+index.rank_1(pos);}else{pos=index.rank_0(pos);}}ret}pub fn rank(&self,num:usize,mut 
            pos:usize)->usize{if self.sorted_positions.get(num).unwrap_or(&None).is_none(){return 0;}assert!(pos<=self.len);for(ln,index)in self
            .indices.iter().enumerate().rev(){let bit=(num>>ln)&1;if bit==1{pos=index.rank0_all()+index.rank_1(pos);}else{pos=index.rank_0(pos);}}pos
            -self.sorted_positions[num].unwrap()}pub fn rank_less_eq_more<R:RangeBounds<usize>>(&self,num:usize,range:R,)->(usize,usize,usize){let(mut 
            begin,mut end)=self.get_pos_range(range);let range_len=end-begin;if num>self.max{return(range_len,0,0);}let mut less=0;let mut more=0;for
            (ln,index)in self.indices.iter().enumerate().rev(){let bit=(num>>ln)&1;let rank1_begin=index.rank_1(begin);let rank1_end=index.rank_1(end
            );let rank0_begin=begin-rank1_begin;let rank0_end=end-rank1_end;if bit==1{less+=rank0_end-rank0_begin;begin=index.rank0_all()+rank1_begin
            ;end=index.rank0_all()+rank1_end;}else{more+=rank1_end-rank1_begin;begin=rank0_begin;end=rank0_end;}}let eq=range_len-less-more;(less,eq
            ,more)}pub fn select(&self,num:usize,pos:usize)->Option<usize>{if pos>=*self.counts.get(num)?{return None;}let mut ret=self
            .sorted_positions[num].unwrap()+pos;for(ln,index)in self.indices.iter().enumerate(){let bit=(num>>ln)&1;if bit==1{ret=index.select_1(ret
            -index.rank0_all()).unwrap();}else{ret=index.select_0(ret).unwrap();}}Some(ret)}fn get_pos_range<R:RangeBounds<usize>>(&self,range:R
            )->(usize,usize){use std::ops::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,};let right
            =match range.end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.len,};assert!(left<=right&&right<=self.len);(left,right)}pub fn 
            quantile<R:RangeBounds<usize>>(&self,range:R,mut k:usize)->usize{let(mut begin,mut end)=self.get_pos_range(range);assert!(k<end-begin);let 
            mut ret=0;for(ln,index)in self.indices.iter().enumerate().rev(){let one_cnt=index.rank_1(end)-index.rank_1(begin);let zero_cnt=end-begin
            -one_cnt;if k<zero_cnt{begin=index.rank_0(begin);end=index.rank_0(end);}else{ret|=1<<ln;k-=zero_cnt;begin=index.rank0_all()+index.rank_1
            (begin);end=index.rank0_all()+index.rank_1(end);}}ret}fn get_num_range<R:RangeBounds<usize>>(&self,range:R)->(usize,usize){use std::ops
            ::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,}.min(self.max+1);let right=match range
            .end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.max+1,}.min(self.max+1);assert!(left<=right);(left,right)}pub fn range_freq
            <R1:RangeBounds<usize>+Clone,R2:RangeBounds<usize>>(&self,pos_range:R1,num_range:R2,)->usize{let(num_begin,num_end)=self.get_num_range
            (num_range);if num_begin>=num_end{return 0;}let cnt_begin=self.rank_less_eq_more(num_begin,pos_range.clone()).0;let cnt_end=self
            .rank_less_eq_more(num_end,pos_range).0;cnt_end-cnt_begin}pub fn next_value<R:RangeBounds<usize>+Clone>(&self,range:R,lower:usize
            ,)->Option<usize>{let(less,eq,upper)=self.rank_less_eq_more(lower,range.clone());if eq>0{return Some(lower);}if upper==0{return None;}Some
            (self.quantile(range,less))}pub fn prev_value<R:RangeBounds<usize>+Clone>(&self,range:R,upper:usize,)->Option<usize>{let less=self
            .rank_less_eq_more(upper,range.clone()).0;if less==0{return None;}Some(self.quantile(range,less-1))}}}
        pub mod wavelet_matrix_rect_sum {use crate::__cargo_equip::preludes::wavelet_matrix_rect_sum::*;use bitvec::BitVec;use internal_bits
            ::ceil_log2;use internal_type_traits::Integral;use std::ops::RangeBounds;#[derive(Debug,Clone)]pub struct WaveletMatrixRectSum<T:Integral
            >{max:usize,len:usize,indices:Vec<BitVec>,cum_sum:Vec<Vec<T>>,raw_cum_sum:Vec<T>,}impl<T:Integral>WaveletMatrixRectSum<T>{pub fn new
            (compressed_list:&[usize],weight_list:&[T])->Self{assert_eq!(compressed_list.len(),weight_list.len());let len=compressed_list.len();let 
            mut raw_cum_sum=vec![T::zero();len+1];for(i,&w)in weight_list.iter().enumerate(){raw_cum_sum[i+1]=raw_cum_sum[i]+w;}let max
            =*compressed_list.iter().max().unwrap_or(&0);let log=ceil_log2(max as u32+1)as usize;let mut indices=vec![BitVec::new(len);log];let mut 
            tmp=vec![Vec::with_capacity(len);2];let mut list=compressed_list.to_vec();let mut weight_list=weight_list.to_vec();let mut tmp_weight
            =vec![Vec::with_capacity(len);2];let mut cum_sum=vec![vec![T::zero();len+1];log];for(ln,index)in indices.iter_mut().enumerate().rev(){for
            (x,(&y,&w))in list.iter().zip(weight_list.iter()).enumerate(){if(y>>ln)&1==1{index.set(x);tmp[1].push(y);tmp_weight[1].push(w
            );}else{tmp[0].push(y);tmp_weight[0].push(w);}}index.build();list.clear();weight_list.clear();list.append(&mut tmp[0]);list.append(&mut 
            tmp[1]);weight_list.append(&mut tmp_weight[0]);weight_list.append(&mut tmp_weight[1]);for(i,&w)in weight_list.iter().enumerate
            (){cum_sum[ln][i+1]=cum_sum[ln][i]+w;}}Self{max,len,indices,cum_sum,raw_cum_sum,}}fn get_pos_range<R:RangeBounds<usize>>(&self,range:R
            )->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,};let r=match range
            .end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.len,};assert!(l<=r&&r<=self.len);(l,r)}fn get_num_range<R:RangeBounds<usize
            >>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let l=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,}
            .min(self.max+1);let r=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.max+1,}.min(self.max+1);assert!(l<=r);(l
            ,r)}fn rect_sum_sub<R:RangeBounds<usize>>(&self,x_range:R,upper:usize)->T{if upper==0{return T::zero();}let(mut begin,mut end)=self
            .get_pos_range(x_range);if upper>self.max{return self.raw_cum_sum[end]-self.raw_cum_sum[begin];}let mut ret=T::zero();for(ln,index)in self
            .indices.iter().enumerate().rev(){let bit=(upper>>ln)&1;let rank1_begin=index.rank_1(begin);let rank1_end=index.rank_1(end);let 
            rank0_begin=begin-rank1_begin;let rank0_end=end-rank1_end;if bit==1{ret+=self.cum_sum[ln][rank0_end]-self.cum_sum[ln][rank0_begin];begin
            =index.rank0_all()+rank1_begin;end=index.rank0_all()+rank1_end;}else{begin=rank0_begin;end=rank0_end;}}ret}pub fn rect_sum<R1:RangeBounds
            <usize>+Clone,R2:RangeBounds<usize>>(&self,x_range:R1,y_range:R2,)->T{let(begin,end)=self.get_num_range(y_range);self.rect_sum_sub(x_range
            .clone(),end)-self.rect_sum_sub(x_range,begin)}}}
    }
    pub(crate) mod macros {
        pub mod __bitvec_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod wavelet_matrix {}
        pub mod wavelet_matrix_rect_sum {}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
    mod preludes {
        pub mod __bitvec_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod wavelet_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__bitvec_0_1_0 as bitvec,__internal_bits_0_1_0 as 
            internal_bits};}
        pub mod wavelet_matrix_rect_sum {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__bitvec_0_1_0 as bitvec,__internal_bits_0_1_0 
            as internal_bits,__internal_type_traits_0_1_0 as internal_type_traits};}
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0