#1019372 (Rust) No.1625 三角形の質問

• 問題: No.1625 三角形の質問
• ユーザー: CoCo_Japan_pan
• 提出日時: 2024-10-14 11:03:08
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 679 ms / 6,000 ms
• コード長: 18,699 bytes
• コンパイル時間: 22,131 ms
• コンパイル使用メモリ: 378,896 KB
• 実行使用メモリ: 104,332 KB
• 最終ジャッジ日時: 2024-10-14 11:03:42
• 合計ジャッジ時間: 25,947 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	25 ms; 7,936 KB
testcase_02	AC	247 ms; 30,336 KB
testcase_03	AC	175 ms; 51,584 KB
testcase_04	AC	155 ms; 28,032 KB
testcase_05	AC	309 ms; 56,064 KB
testcase_06	AC	662 ms; 104,064 KB
testcase_07	AC	631 ms; 104,064 KB
testcase_08	AC	677 ms; 104,064 KB
testcase_09	AC	637 ms; 104,192 KB
testcase_10	AC	665 ms; 104,192 KB
testcase_11	AC	640 ms; 104,192 KB
testcase_12	AC	662 ms; 104,064 KB
testcase_13	AC	679 ms; 104,000 KB
testcase_14	AC	613 ms; 103,992 KB
testcase_15	AC	649 ms; 104,192 KB
testcase_16	AC	101 ms; 32,192 KB
testcase_17	AC	320 ms; 99,072 KB
testcase_18	AC	44 ms; 13,824 KB
testcase_19	AC	367 ms; 104,332 KB

ソースコード

// verification-helper: PROBLEM https://yukicoder.me/problems/no/1625

pub use __cargo_equip::prelude::*;

use algebra::{Commutative, Monoid};
use proconio::{fastout, input};
use wavelet_matrix_segtree::WaveletMatrixSegTree;

#[derive(Clone, Copy, Debug)]
enum Query {
    Add(i64, i64, i64),
    Get(i64, i64),
}

#[derive(Clone, Copy, Debug)]
enum MaxMonoid {}
impl Monoid for MaxMonoid {
    type Target = i64;
    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target {
        *a.max(b)
    }
    fn id_element() -> Self::Target {
        -1
    }
}
impl Commutative for MaxMonoid {}

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        a_b_c_d_e_f: [(i64, i64, i64, i64, i64, i64); n],
    }
    let mut queries = a_b_c_d_e_f.into_iter().map(l_r_area).collect::<Vec<_>>();
    for _ in 0..q {
        input! {
            query_type: u8,
        }
        if query_type == 1 {
            input! {
                add: (i64, i64, i64, i64, i64, i64)
            }
            queries.push(l_r_area(add));
        } else {
            input! {
                l: i64,
                r: i64,
            }
            queries.push(Query::Get(l, r));
        }
    }
    let queries = queries;
    let x_y = {
        let mut x_y = queries
            .iter()
            .filter_map(|query| match query {
                Query::Add(x, y, _) => Some((*x, *y)),
                Query::Get(_, _) => None,
            })
            .collect::<Vec<_>>();
        x_y.sort_unstable();
        x_y.dedup();
        x_y
    };
    let init_weight = {
        let mut init_weight = vec![-1; x_y.len()];
        for query in queries.iter().take(n) {
            if let Query::Add(x, y, area) = query {
                let id = x_y.binary_search(&(*x, *y)).unwrap();
                init_weight[id] = init_weight[id].max(*area);
            }
        }
        init_weight
    };
    let y = x_y.iter().map(|(_, y)| *y).collect::<Vec<_>>();
    let sorted_y = {
        let mut sorted_y = y.clone();
        sorted_y.sort_unstable();
        sorted_y.dedup();
        sorted_y
    };
    let y = y
        .into_iter()
        .map(|y| sorted_y.binary_search(&y).unwrap())
        .collect::<Vec<_>>();
    let mut wm_seg = WaveletMatrixSegTree::<MaxMonoid>::from_weight(&y, &init_weight);
    for query in queries.into_iter().skip(n) {
        match query {
            Query::Add(x, y, area) => {
                let id = x_y.binary_search(&(x, y)).unwrap();
                let old_val = wm_seg.get_weight(id);
                wm_seg.set(id, old_val.max(area));
            }
            Query::Get(l, r) => {
                let xl = x_y.partition_point(|&(x, _)| x < l);
                let xr = x_y.partition_point(|&(x, _)| x <= r);
                let yl = sorted_y.partition_point(|&y| y < l);
                let yr = sorted_y.partition_point(|&y| y <= r);
                let ans = wm_seg.rect_sum_monoid(xl..xr, yl..yr);
                println!("{}", ans);
            }
        }
    }
}

fn l_r_area(x: (i64, i64, i64, i64, i64, i64)) -> Query {
    let x_list = [x.0, x.2, x.4];
    let left = *x_list.iter().min().unwrap();
    let right = *x_list.iter().max().unwrap();
    let y_list = [x.1, x.3, x.5];
    let x_list_parralel = x_list
        .into_iter()
        .map(|x| x - x_list[0])
        .collect::<Vec<_>>();
    let y_list_parralel = y_list
        .into_iter()
        .map(|y| y - y_list[0])
        .collect::<Vec<_>>();
    let area =
        (x_list_parralel[1] * y_list_parralel[2] - x_list_parralel[2] * y_list_parralel[1]).abs();
    Query::Add(left, right, area)
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `algebra 0.1.0 (path+████████████████████████████████████████████████████)`                                       published in ssh://[e-mail]/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebra`
///  - `bitdict 0.1.0 (path+████████████████████████████████████████████████████████████)`                               published in ssh://[e-mail]/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitdict_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`
///  - `segtree 0.1.0 (path+███████████████████████████████████████████████████████████████████)`                        published in ssh://[e-mail]/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__segtree_0_1_0`
///  - `wavelet_matrix_segtree 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)` published in ssh://[e-mail]/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix_segtree`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebra {use std::fmt::Debug;pub trait Commutative{}pub trait NonCommutative{}pub trait Action:Debug+Clone{type Target:Clone;fn id_action()->Self;fn composition(&mut self,rhs:&Self);fn apply(&self,target:&mut Self::Target);}pub trait Monoid{type Target:Debug+Clone+Eq;fn id_element()->Self::Target;fn binary_operation(a:&Self::Target,b:&Self::Target)->Self::Target;}pub trait ActionMonoid{type Monoid:Monoid;type Action:Action<Target=<Self::Monoid as Monoid>::Target>;fn id_element()-><Self::Monoid as Monoid>::Target{Self::Monoid::id_element()}fn binary_operation(a:&<Self::Monoid as Monoid>::Target,b:&<Self::Monoid as Monoid>::Target,)-><Self::Monoid as Monoid>::Target{Self::Monoid::binary_operation(a,b)}fn id_action()->Self::Action{Self::Action::id_action()}fn composition(f:&mut Self::Action,g:&Self::Action){f.composition(g)}fn apply(x:&mut<Self::Monoid as Monoid>::Target,f:&Self::Action){f.apply(x)}}pub trait IdempotentMonoid:Monoid{}pub trait Group:Monoid{fn inverse(a:&Self::Target)->Self::Target;}pub trait Semiring:Debug+Clone+Eq{type Target:Debug+Clone+Eq;fn zero()->Self::Target;fn one()->Self::Target;fn add_assign(a:&mut Self::Target,b:&Self::Target);fn mul(a:&Self::Target,b:&Self::Target)->Self::Target;}}
        pub mod __bitdict_0_1_0 {#[derive(Debug,Clone,Copy)]struct Block{bit:u64,cum_sum_popcnt:u32,}#[derive(Debug,Clone)]pub struct BitDict{len:usize,blocks:Vec<Block>,all_popcnt:usize,one_select:Vec<u32>,zero_select:Vec<u32>,}impl From<&[bool]>for BitDict{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 BitDict{pub fn new(len:usize)->Self{Self{len,blocks:vec![Block{bit: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].bit>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i<self.len);self.blocks[i>>6].bit|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.bit.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.bit.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{bit: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].bit,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].bit,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 __segtree_0_1_0 {use crate::__cargo_equip::preludes::__segtree_0_1_0::*;use algebra::Monoid;use internal_bits::ceil_log2;use std::ops::RangeBounds;#[derive(Debug,Clone,PartialEq,Eq)]pub struct SegTree<M:Monoid>{range_size:usize,leaf_size:usize,log:usize,data:Vec<M::Target>,}impl<M:Monoid>From<&Vec<M::Target>>for SegTree<M>{fn from(v:&Vec<M::Target>)->Self{let range_size=v.len();let log=ceil_log2(range_size as u32)as usize;let leaf_size=1<<log;let mut data=vec![M::id_element();leaf_size*2];data[leaf_size..leaf_size+range_size].clone_from_slice(v);let mut seg_tree=SegTree{range_size,leaf_size,log,data,};for i in(1..leaf_size).rev(){seg_tree.update(i);}seg_tree}}impl<M:Monoid>SegTree<M>{pub fn new(n:usize)->Self{(&vec![M::id_element();n]).into()}pub fn set(&mut self,mut p:usize,x:M::Target){assert!(p<self.range_size);p+=self.leaf_size;self.data[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&self,p:usize)->M::Target{assert!(p<self.range_size);self.data[p+self.leaf_size].clone()}pub fn prod<R:RangeBounds<usize>>(&self,range:R)->M::Target{let mut l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+1,std::ops::Bound::Unbounded=>0,};let mut r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+1,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>self.range_size,};assert!(l<=r&&r<=self.range_size);if l==0&&r==self.range_size{return self.all_prod();}l+=self.leaf_size;r+=self.leaf_size;let mut sml=M::id_element();let mut smr=M::id_element();while l<r{if l&1!=0{sml=M::binary_operation(&sml,&self.data[l]);l+=1;}if r&1!=0{r-=1;smr=M::binary_operation(&self.data[r],&smr);}l>>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::Target{self.data[1].clone()}pub fn max_right<F>(&self,mut l:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(l<=self.range_size);assert!(f(&M::id_element()));if l==self.range_size{return self.range_size;}l+=self.leaf_size;let mut sm=M::id_element();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.data[l])){while l<self.leaf_size{l>>=1;let res=M::binary_operation(&sm,&self.data[l]);if f(&res){sm=res;l+=1;}}return l-self.leaf_size;}sm=M::binary_operation(&sm,&self.data[l]);l+=1;{let l=l as isize;(l&-l)!=l}}{}self.range_size}pub fn min_left<F>(&self,mut r:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(r<=self.range_size);assert!(f(&M::id_element()));if r==0{return 0;}r+=self.leaf_size;let mut sm=M::id_element();while{r-=1;while r>1&&r%2!=0{r>>=1;}if!f(&M::binary_operation(&self.data[r],&sm)){while r<self.leaf_size{r=2*r+1;let res=M::binary_operation(&self.data[r],&sm);if f(&res){sm=res;r-=1;}}return r+1-self.leaf_size;}sm=M::binary_operation(&self.data[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}}impl<M:Monoid>SegTree<M>{fn update(&mut self,k:usize){self.data[k]=M::binary_operation(&self.data[k*2],&self.data[k*2+1]);}}}
        pub mod wavelet_matrix_segtree {use crate::__cargo_equip::preludes::wavelet_matrix_segtree::*;use algebra::{Commutative,Group,Monoid};use bitdict::BitDict;use internal_bits::ceil_log2;use segtree::SegTree;use std::ops::RangeBounds;pub struct WaveletMatrixSegTree<M:Monoid+Commutative>{upper_bound:usize,len:usize,indices:Vec<BitDict>,segtree_per_bit:Vec<SegTree<M>>,}impl<M:Monoid+Commutative>WaveletMatrixSegTree<M>{pub fn from_weight(compressed_list:&[usize],weight_list:&[M::Target])->Self{assert_eq!(compressed_list.len(),weight_list.len());let len=compressed_list.len();let upper_bound=*compressed_list.iter().max().unwrap_or(&0)+1;let log=ceil_log2(upper_bound as u32+1)as usize;let mut indices=vec![BitDict::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 segtree_per_bit=Vec::with_capacity(log);for(ln,index)in indices.iter_mut().enumerate().rev(){for(x,(y,w))in list.drain(..).zip(weight_list.drain(..)).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.append(&mut tmp[0]);list.append(&mut tmp[1]);weight_list.append(&mut tmp_weight[0]);weight_list.append(&mut tmp_weight[1]);segtree_per_bit.push(SegTree::from(&weight_list));}segtree_per_bit.reverse();Self{upper_bound,len,indices,segtree_per_bit,}}pub fn from_identity(compressed_list:&[usize])->Self{let weight_list=vec![M::id_element();compressed_list.len()];Self::from_weight(compressed_list,&weight_list)}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.upper_bound);let r=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.upper_bound,}.min(self.upper_bound);assert!(l<=r);(l,r)}pub fn prefix_rect_sum<R:RangeBounds<usize>>(&self,x_range:R,upper:usize)->M::Target{if upper==0{return M::id_element();}let(mut begin,mut end)=self.get_pos_range(x_range);let mut ret=M::id_element();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=M::binary_operation(&ret,&self.segtree_per_bit[ln].prod(rank0_begin..rank0_end),);begin=index.rank0_all()+rank1_begin;end=index.rank0_all()+rank1_end;}else{begin=rank0_begin;end=rank0_end;}}ret}pub fn rect_sum_group<R1:RangeBounds<usize>+Clone,R2:RangeBounds<usize>>(&self,x_range:R1,y_range:R2,)->M::Target where M:Group,{let(begin,end)=self.get_num_range(y_range);let s2=self.prefix_rect_sum(x_range.clone(),end);let s1=self.prefix_rect_sum(x_range,begin);M::binary_operation(&M::inverse(&s1),&s2)}pub fn rect_sum_monoid<R1:RangeBounds<usize>,R2:RangeBounds<usize>>(&self,x_range:R1,y_range:R2,)->M::Target{let(xl,xr)=self.get_pos_range(x_range);let(y_low,y_hi)=self.get_num_range(y_range);let mut ret=M::id_element();let ln=self.indices.len();self.dfs(&mut ret,ln,xl,xr,0,1<<ln,y_low,y_hi);ret}#[allow(clippy::too_many_arguments)]fn dfs(&self,ret:&mut M::Target,ln:usize,xl:usize,xr:usize,yl:usize,yr:usize,y_low:usize,y_hi:usize,){assert_eq!(yr-yl,1<<ln);if y_hi<=yl||yr<=y_low{return;}if y_low<=yl&&yr<=y_hi{*ret=M::binary_operation(ret,&self.segtree_per_bit[ln].prod(xl..xr));return;}let ln=ln-1;let rank1_xl=self.indices[ln].rank_1(xl);let rank1_xr=self.indices[ln].rank_1(xr);let rank0_all=self.indices[ln].rank0_all();let rank0_xl=xl-rank1_xl;let rank0_xr=xr-rank1_xr;let ymid=(yl+yr)/2;self.dfs(ret,ln,rank0_xl,rank0_xr,yl,ymid,y_low,y_hi);self.dfs(ret,ln,rank0_all+rank1_xl,rank0_all+rank1_xr,ymid,yr,y_low,y_hi,);}pub fn set(&mut self,mut x:usize,new_val:M::Target){assert!(x<self.len);for(ln,index)in self.indices.iter().enumerate().rev(){let bit=index.access(x);if bit{x=index.rank0_all()+index.rank_1(x);}else{x=index.rank_0(x);}self.segtree_per_bit[ln].set(x,new_val.clone());}}pub fn get_weight(&self,x:usize)->M::Target{assert!(x<self.len);let index=self.indices.last().unwrap();let x=if index.access(x){index.rank0_all()+index.rank_1(x)}else{index.rank_0(x)};self.segtree_per_bit.last().unwrap().get(x)}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __segtree_0_1_0 {}
        pub mod wavelet_matrix_segtree {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod algebra {}
        pub mod __bitdict_0_1_0 {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __segtree_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__internal_bits_0_1_0 as internal_bits};}
        pub mod wavelet_matrix_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__bitdict_0_1_0 as bitdict,__internal_bits_0_1_0 as internal_bits,__segtree_0_1_0 as segtree};}
    }
}