結果

問題 No.1625 三角形の質問
ユーザー CoCo_Japan_panCoCo_Japan_pan
提出日時 2024-10-12 20:48:36
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 2,468 ms / 6,000 ms
コード長 14,737 bytes
コンパイル時間 15,658 ms
コンパイル使用メモリ 378,000 KB
実行使用メモリ 155,200 KB
最終ジャッジ日時 2024-10-12 20:49:30
合計ジャッジ時間 49,823 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 62 ms
11,776 KB
testcase_02 AC 666 ms
52,696 KB
testcase_03 AC 842 ms
65,800 KB
testcase_04 AC 546 ms
44,248 KB
testcase_05 AC 1,426 ms
91,160 KB
testcase_06 AC 2,376 ms
131,176 KB
testcase_07 AC 2,374 ms
131,344 KB
testcase_08 AC 2,310 ms
129,520 KB
testcase_09 AC 2,348 ms
133,040 KB
testcase_10 AC 2,362 ms
128,556 KB
testcase_11 AC 2,291 ms
131,884 KB
testcase_12 AC 2,275 ms
131,440 KB
testcase_13 AC 2,468 ms
131,060 KB
testcase_14 AC 2,423 ms
130,952 KB
testcase_15 AC 2,332 ms
129,032 KB
testcase_16 AC 221 ms
50,444 KB
testcase_17 AC 539 ms
123,904 KB
testcase_18 AC 50 ms
15,360 KB
testcase_19 AC 687 ms
155,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

pub use __cargo_equip::prelude::*;

use algebra::{Commutative, Monoid};
use proconio::{fastout, input};
use segtree_2d_compressed::SegTree2DCompressed;

#[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: i64,
        }
        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 update_queries = queries
        .iter()
        .filter_map(|query| match query {
            Query::Add(l, r, _) => Some((*l, *r)),
            _ => None,
        })
        .collect::<Vec<_>>();
    let mut segtree = SegTree2DCompressed::<MaxMonoid, i64>::new(&update_queries);
    for query in queries {
        match query {
            Query::Add(l, r, area) => segtree.add(l, r, area),
            Query::Get(l, r) => println!("{}", segtree.prod(l..=r, l..=r)),
        }
    }
}

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://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebra`
///  - `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`
///  - `segtree 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::__segtree_0_1_0`
///  - `segtree_2d_compressed 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::segtree_2d_compressed`
#[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 __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 __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 segtree_2d_compressed {use crate::__cargo_equip::preludes::segtree_2d_compressed::*;use algebra::{Commutative,Monoid};use internal_type_traits::Integral;use segtree::SegTree;use std::ops::{Range,RangeBounds};#[derive(Debug)]pub struct SegTree2DCompressed<M:Monoid+Commutative,T:Integral>{height_compressed:Vec<T>,width_compressed:Vec<Vec<T>>,data:Vec<SegTree<M>>,}impl<M:Monoid+Commutative,T:Integral>SegTree2DCompressed<M,T>{pub fn new(update_queries:&[(T,T)])->Self{let height_compressed={let mut tmp=update_queries.iter().map(|&(h,_)|h).collect::<Vec<_>>();tmp.sort_unstable();tmp.dedup();tmp};let width_compressed={let mut tmp=vec![vec![];height_compressed.len()*2];for&(h,w)in update_queries.iter(){let h=height_compressed.binary_search(&h).unwrap()+height_compressed.len();tmp[h].push(w);}for v in tmp.iter_mut(){v.sort_unstable();v.dedup();}for h in(1..height_compressed.len()).rev(){let child_left=tmp[h*2].clone();let child_right=tmp[h*2+1].clone();tmp[h]=child_left.into_iter().chain(child_right).collect();tmp[h].sort_unstable();tmp[h].dedup();}tmp};let data=(0..height_compressed.len()*2).map(|i|SegTree::<M>::new(width_compressed[i].len())).collect();Self{height_compressed,width_compressed,data,}}pub fn get(&self,h:T,w:T)->M::Target{if let Ok(h)=self.height_compressed.binary_search(&h){let h=h+self.height_compressed.len();if let Ok(w)=self.width_compressed[h].binary_search(&w){return self.data[h].get(w);}}M::id_element()}pub fn add(&mut self,h:T,w:T,val:M::Target){let mut h=self.height_compressed.binary_search(&h).expect("h is not in update_queries");h+=self.height_compressed.len();while h>0{let cur_w_id=self.width_compressed[h].binary_search(&w).expect("w is not in update_queries");let old_val=self.data[h].get(cur_w_id);self.data[h].set(cur_w_id,M::binary_operation(&old_val,&val));h>>=1;}}#[allow(clippy::collapsible_else_if,clippy::redundant_clone)]pub fn set(&mut self,h:T,w:T,val:M::Target){let mut h=self.height_compressed.binary_search(&h).expect("h is not in update_queries");h+=self.height_compressed.len();let mut pre_h=2*h;let mut pre_val=val.clone();while h>0{let cur_w_id=self.width_compressed[h].binary_search(&w).expect("w is not in update_queries");if h>=self.height_compressed.len(){self.data[h].set(cur_w_id,val.clone());}else{let other_child=if pre_h==2*h{if let Ok(w)=self.width_compressed[2*h+1].binary_search(&w){self.data[2*h+1].get(w)}else{M::id_element()}}else{if let Ok(w)=self.width_compressed[2*h].binary_search(&w){self.data[2*h].get(w)}else{M::id_element()}};let new_val=M::binary_operation(&pre_val,&other_child);pre_val=new_val.clone();self.data[h].set(cur_w_id,new_val);}pre_h=h;h>>=1;}}pub fn prod<R1:RangeBounds<T>,R2:RangeBounds<T>>(&self,height_range:R1,width_range:R2,)->M::Target{let height_left=match height_range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+T::one(),std::ops::Bound::Unbounded=>T::min_value(),};let height_right=match height_range.end_bound(){std::ops::Bound::Included(&r)=>r+T::one(),std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>T::max_value(),};assert!(height_left<=height_right);let mut height_left=self.height_compressed.partition_point(|&h|h<height_left);let mut height_right=self.height_compressed.partition_point(|&h|h<height_right);height_left+=self.height_compressed.len();height_right+=self.height_compressed.len();let mut ret=M::id_element();while height_left<height_right{if height_left&1!=0{let w_range=self.calc_row_range(height_left,&width_range);ret=M::binary_operation(&ret,&self.data[height_left].prod(w_range));height_left+=1;}if height_right&1!=0{height_right-=1;let w_range=self.calc_row_range(height_right,&width_range);ret=M::binary_operation(&ret,&self.data[height_right].prod(w_range));}height_left>>=1;height_right>>=1;}ret}fn calc_row_range<R1:RangeBounds<T>>(&self,h:usize,width_range:&R1)->Range<usize>{let w_left=match width_range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+T::one(),std::ops::Bound::Unbounded=>T::min_value(),};let w_right=match width_range.end_bound(){std::ops::Bound::Included(&r)=>r+T::one(),std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>T::max_value(),};let w_left=self.width_compressed[h].partition_point(|&w|w<w_left);let w_right=self.width_compressed[h].partition_point(|&w|w<w_right);w_left..w_right}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __segtree_0_1_0 {}
        pub mod segtree_2d_compressed {}
    }

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

    mod preludes {
        pub mod algebra {}
        pub mod __internal_bits_0_1_0 {}
        pub mod __internal_type_traits_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 segtree_2d_compressed {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__internal_type_traits_0_1_0 as internal_type_traits,__segtree_0_1_0 as segtree};}
    }
}
0