結果

問題 No.738 平らな農地
ユーザー CoCo_Japan_panCoCo_Japan_pan
提出日時 2024-10-01 22:23:05
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 3 ms
6,820 KB
testcase_06 AC 4 ms
6,816 KB
testcase_07 AC 4 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 1 ms
6,816 KB
testcase_13 AC 3 ms
6,816 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 108 ms
22,800 KB
testcase_16 AC 113 ms
23,128 KB
testcase_17 AC 123 ms
23,096 KB
testcase_18 AC 119 ms
22,632 KB
testcase_19 AC 146 ms
24,260 KB
testcase_20 AC 112 ms
23,140 KB
testcase_21 AC 134 ms
24,428 KB
testcase_22 AC 115 ms
23,280 KB
testcase_23 AC 132 ms
23,772 KB
testcase_24 AC 133 ms
23,292 KB
testcase_25 AC 1 ms
6,820 KB
testcase_26 AC 2 ms
6,820 KB
testcase_27 AC 1 ms
6,820 KB
testcase_28 AC 2 ms
6,820 KB
testcase_29 AC 2 ms
6,820 KB
testcase_30 AC 1 ms
6,820 KB
testcase_31 AC 1 ms
6,820 KB
testcase_32 AC 1 ms
6,816 KB
testcase_33 AC 2 ms
6,820 KB
testcase_34 AC 2 ms
6,820 KB
testcase_35 AC 2 ms
6,816 KB
testcase_36 AC 1 ms
6,816 KB
testcase_37 AC 1 ms
6,816 KB
testcase_38 AC 2 ms
6,816 KB
testcase_39 AC 1 ms
6,820 KB
testcase_40 AC 2 ms
6,820 KB
testcase_41 AC 2 ms
6,820 KB
testcase_42 AC 1 ms
6,816 KB
testcase_43 AC 1 ms
6,820 KB
testcase_44 AC 1 ms
6,816 KB
testcase_45 AC 115 ms
26,124 KB
testcase_46 AC 106 ms
22,408 KB
testcase_47 AC 113 ms
25,592 KB
testcase_48 AC 98 ms
22,892 KB
testcase_49 AC 97 ms
22,588 KB
testcase_50 AC 104 ms
25,324 KB
testcase_51 AC 117 ms
25,620 KB
testcase_52 AC 103 ms
22,724 KB
testcase_53 AC 112 ms
24,836 KB
testcase_54 AC 117 ms
25,648 KB
testcase_55 AC 119 ms
25,504 KB
testcase_56 AC 116 ms
25,292 KB
testcase_57 AC 102 ms
22,368 KB
testcase_58 AC 111 ms
25,140 KB
testcase_59 AC 112 ms
26,136 KB
testcase_60 AC 109 ms
25,956 KB
testcase_61 AC 110 ms
25,796 KB
testcase_62 AC 100 ms
22,532 KB
testcase_63 AC 122 ms
26,136 KB
testcase_64 AC 116 ms
25,796 KB
testcase_65 AC 180 ms
23,120 KB
testcase_66 AC 218 ms
23,944 KB
testcase_67 AC 98 ms
24,744 KB
testcase_68 AC 97 ms
25,440 KB
testcase_69 AC 136 ms
25,792 KB
testcase_70 AC 116 ms
26,516 KB
testcase_71 AC 11 ms
6,912 KB
testcase_72 AC 13 ms
7,412 KB
testcase_73 AC 12 ms
7,272 KB
testcase_74 AC 14 ms
7,480 KB
testcase_75 AC 126 ms
24,408 KB
testcase_76 AC 107 ms
25,436 KB
testcase_77 AC 141 ms
24,572 KB
testcase_78 AC 152 ms
26,468 KB
testcase_79 AC 154 ms
26,644 KB
testcase_80 AC 122 ms
25,620 KB
testcase_81 AC 138 ms
24,916 KB
testcase_82 AC 143 ms
25,804 KB
testcase_83 AC 18 ms
10,232 KB
testcase_84 AC 27 ms
10,008 KB
testcase_85 AC 204 ms
26,244 KB
testcase_86 AC 183 ms
24,352 KB
testcase_87 AC 77 ms
25,396 KB
testcase_88 AC 73 ms
24,484 KB
testcase_89 AC 1 ms
6,820 KB
testcase_90 AC 1 ms
6,820 KB
testcase_91 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

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};}
    }
}
0