結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
|
提出日時 | 2024-02-23 22:26:59 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 195 ms / 2,500 ms |
コード長 | 20,519 bytes |
コンパイル時間 | 13,922 ms |
コンパイル使用メモリ | 384,044 KB |
実行使用メモリ | 24,760 KB |
最終ジャッジ日時 | 2024-09-29 07:20:48 |
合計ジャッジ時間 | 20,613 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#![allow(non_snake_case)]#![allow(unused_imports)]#![allow(unused_macros)]#![allow(clippy::needless_range_loop)]#![allow(clippy::comparison_chain)]#![allow(clippy::nonminimal_bool)]#![allow(clippy::neg_multiply)]#![allow(dead_code)]use std::cmp::Reverse;use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};const INF: usize = 1_usize << 60;#[derive(Default)]struct Solver {}impl Solver {fn solve(&mut self) {input! {N: usize,_A: usize,mut X: [usize; N],T: usize,mut LR: [(usize, usize); T]}let mut v = vec![];for &x in &X {v.push(x);}for &(l, r) in &LR {v.push(l);v.push(r);}let mp = coordinate_compression(v);let A = *mp.last_key_value().unwrap().1 + 1;for i in 0..N {X[i] = mp[&X[i]];}for i in 0..T {LR[i] = (mp[&LR[i].0], mp[&LR[i].1]);}let a = vec![INF; A + 1];let mut seg: LazySegtree<Mono> = a.into();for (t, &(l, r)) in LR.iter().enumerate() {seg.apply_range(l..=r, t + 1);}for &x in &X {let ans = seg.get(x);if ans == INF {println!("-1");} else {println!("{}", ans);}}}}fn coordinate_compression<T: std::cmp::Ord + Copy>(v: Vec<T>) -> BTreeMap<T, usize> {let mut vv = v;vv.sort();vv.dedup();let ret = vv.iter().enumerate().map(|(i, &s)| (s, i)).collect();ret}struct Mono;impl Monoid for Mono {type S = usize;fn identity() -> Self::S {INF}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a.min(b)}}impl MapMonoid for Mono {type M = Mono;type F = usize;fn identity_map() -> Self::F {INF}fn mapping(&f: &usize, &x: &usize) -> usize {if f == INF {x} else {f}}fn composition(&f: &usize, &g: &usize) -> usize {if f == INF {g} else {f}}}fn ceil_pow2(n: u32) -> u32 {32 - n.saturating_sub(1).leading_zeros()}pub trait Integral:'static+ Send+ Sync+ Copy+ Ord+ std::ops::Not<Output = Self>+ std::ops::Add<Output = Self>+ std::ops::Sub<Output = Self>+ std::ops::Mul<Output = Self>+ std::ops::Div<Output = Self>+ std::ops::Rem<Output = Self>+ std::ops::AddAssign+ std::ops::SubAssign+ std::ops::MulAssign+ std::ops::DivAssign+ std::ops::RemAssign+ std::iter::Sum+ std::iter::Product+ std::ops::BitOr<Output = Self>+ std::ops::BitAnd<Output = Self>+ std::ops::BitXor<Output = Self>+ std::ops::BitOrAssign+ std::ops::BitAndAssign+ std::ops::BitXorAssign+ std::ops::Shl<Output = Self>+ std::ops::Shr<Output = Self>+ std::ops::ShlAssign+ std::ops::ShrAssign+ std::fmt::Display+ std::fmt::Debug+ std::fmt::Binary+ std::fmt::Octal+ Zero+ One+ BoundedBelow+ BoundedAbove{}/// Class that has additive identity elementpub trait Zero {/// The additive identity elementfn zero() -> Self;}/// Class that has multiplicative identity elementpub trait One {/// The multiplicative identity elementfn 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_value()}}impl BoundedAbove for $ty {#[inline]fn max_value() -> Self {Self::max_value()}}impl Integral for $ty {})*};}impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);pub trait Monoid {type S: Clone;fn identity() -> Self::S;fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;}pub struct Max<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for Max<S>whereS: Copy + Ord + BoundedBelow,{type S = S;fn identity() -> Self::S {S::min_value()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {std::cmp::max(*a, *b)}}pub struct Min<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for Min<S>whereS: Copy + Ord + BoundedAbove,{type S = S;fn identity() -> Self::S {S::max_value()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {std::cmp::min(*a, *b)}}pub struct Additive<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for Additive<S>whereS: Copy + std::ops::Add<Output = S> + Zero,{type S = S;fn identity() -> Self::S {S::zero()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a + *b}}pub struct Multiplicative<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for Multiplicative<S>whereS: Copy + std::ops::Mul<Output = S> + One,{type S = S;fn identity() -> Self::S {S::one()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a * *b}}pub struct BitwiseOr<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for BitwiseOr<S>whereS: Copy + std::ops::BitOr<Output = S> + Zero,{type S = S;fn identity() -> Self::S {S::zero()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a | *b}}pub struct BitwiseAnd<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for BitwiseAnd<S>whereS: Copy + std::ops::BitAnd<Output = S> + std::ops::Not<Output = S> + Zero,{type S = S;fn identity() -> Self::S {!S::zero()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a & *b}}pub struct BitwiseXor<S>(std::convert::Infallible,std::marker::PhantomData<fn() -> S>,);impl<S> Monoid for BitwiseXor<S>whereS: Copy + std::ops::BitXor<Output = S> + Zero,{type S = S;fn identity() -> Self::S {S::zero()}fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {*a ^ *b}}pub trait MapMonoid {type M: Monoid;type F: Clone;// type S = <Self::M as Monoid>::S;fn identity_element() -> <Self::M as Monoid>::S {Self::M::identity()}fn binary_operation(a: &<Self::M as Monoid>::S,b: &<Self::M as Monoid>::S,) -> <Self::M as Monoid>::S {Self::M::binary_operation(a, b)}fn identity_map() -> Self::F;fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S;fn composition(f: &Self::F, g: &Self::F) -> Self::F;}impl<F: MapMonoid> Default for LazySegtree<F> {fn default() -> Self {Self::new(0)}}impl<F: MapMonoid> LazySegtree<F> {pub fn new(n: usize) -> Self {vec![F::identity_element(); n].into()}}impl<F: MapMonoid> From<Vec<<F::M as Monoid>::S>> for LazySegtree<F> {fn from(v: Vec<<F::M as Monoid>::S>) -> Self {let n = v.len();let log = ceil_pow2(n as u32) as usize;let size = 1 << log;let mut d = vec![F::identity_element(); 2 * size];let lz = vec![F::identity_map(); size];d[size..(size + n)].clone_from_slice(&v);let mut ret = LazySegtree {n,size,log,d,lz,};for i in (1..size).rev() {ret.update(i);}ret}}impl<F: MapMonoid> LazySegtree<F> {pub fn set(&mut self, mut p: usize, x: <F::M as Monoid>::S) {assert!(p < self.n);p += self.size;for i in (1..=self.log).rev() {self.push(p >> i);}self.d[p] = x;for i in 1..=self.log {self.update(p >> i);}}pub fn get(&mut self, mut p: usize) -> <F::M as Monoid>::S {assert!(p < self.n);p += self.size;for i in (1..=self.log).rev() {self.push(p >> i);}self.d[p].clone()}pub fn prod<R>(&mut self, range: R) -> <F::M as Monoid>::SwhereR: RangeBounds<usize>,{// Trivial optimizationif range.start_bound() == Bound::Unbounded && range.end_bound() == Bound::Unbounded {return self.all_prod();}let mut r = match range.end_bound() {Bound::Included(r) => r + 1,Bound::Excluded(r) => *r,Bound::Unbounded => self.n,};let mut l = match range.start_bound() {Bound::Included(l) => *l,Bound::Excluded(l) => l + 1,// TODO: There are another way of optimizing [0..r)Bound::Unbounded => 0,};assert!(l <= r && r <= self.n);if l == r {return F::identity_element();}l += self.size;r += self.size;for i in (1..=self.log).rev() {if ((l >> i) << i) != l {self.push(l >> i);}if ((r >> i) << i) != r {self.push(r >> i);}}let mut sml = F::identity_element();let mut smr = F::identity_element();while l < r {if l & 1 != 0 {sml = F::binary_operation(&sml, &self.d[l]);l += 1;}if r & 1 != 0 {r -= 1;smr = F::binary_operation(&self.d[r], &smr);}l >>= 1;r >>= 1;}F::binary_operation(&sml, &smr)}pub fn all_prod(&self) -> <F::M as Monoid>::S {self.d[1].clone()}pub fn apply(&mut self, mut p: usize, f: F::F) {assert!(p < self.n);p += self.size;for i in (1..=self.log).rev() {self.push(p >> i);}self.d[p] = F::mapping(&f, &self.d[p]);for i in 1..=self.log {self.update(p >> i);}}pub fn apply_range<R>(&mut self, range: R, f: F::F)whereR: RangeBounds<usize>,{let mut r = match range.end_bound() {Bound::Included(r) => r + 1,Bound::Excluded(r) => *r,Bound::Unbounded => self.n,};let mut l = match range.start_bound() {Bound::Included(l) => *l,Bound::Excluded(l) => l + 1,// TODO: There are another way of optimizing [0..r)Bound::Unbounded => 0,};assert!(l <= r && r <= self.n);if l == r {return;}l += self.size;r += self.size;for i in (1..=self.log).rev() {if ((l >> i) << i) != l {self.push(l >> i);}if ((r >> i) << i) != r {self.push((r - 1) >> i);}}{let l2 = l;let r2 = r;while l < r {if l & 1 != 0 {self.all_apply(l, f.clone());l += 1;}if r & 1 != 0 {r -= 1;self.all_apply(r, f.clone());}l >>= 1;r >>= 1;}l = l2;r = r2;}for i in 1..=self.log {if ((l >> i) << i) != l {self.update(l >> i);}if ((r >> i) << i) != r {self.update((r - 1) >> i);}}}pub fn max_right<G>(&mut self, mut l: usize, g: G) -> usizewhereG: Fn(<F::M as Monoid>::S) -> bool,{assert!(l <= self.n);assert!(g(F::identity_element()));if l == self.n {return self.n;}l += self.size;for i in (1..=self.log).rev() {self.push(l >> i);}let mut sm = F::identity_element();while {// dowhile l % 2 == 0 {l >>= 1;}if !g(F::binary_operation(&sm, &self.d[l])) {while l < self.size {self.push(l);l *= 2;let res = F::binary_operation(&sm, &self.d[l]);if g(res.clone()) {sm = res;l += 1;}}return l - self.size;}sm = F::binary_operation(&sm, &self.d[l]);l += 1;//while{let l = l as isize;(l & -l) != l}} {}self.n}pub fn min_left<G>(&mut self, mut r: usize, g: G) -> usizewhereG: Fn(<F::M as Monoid>::S) -> bool,{assert!(r <= self.n);assert!(g(F::identity_element()));if r == 0 {return 0;}r += self.size;for i in (1..=self.log).rev() {self.push((r - 1) >> i);}let mut sm = F::identity_element();while {// dor -= 1;while r > 1 && r % 2 != 0 {r >>= 1;}if !g(F::binary_operation(&self.d[r], &sm)) {while r < self.size {self.push(r);r = 2 * r + 1;let res = F::binary_operation(&self.d[r], &sm);if g(res.clone()) {sm = res;r -= 1;}}return r + 1 - self.size;}sm = F::binary_operation(&self.d[r], &sm);// while{let r = r as isize;(r & -r) != r}} {}0}}pub struct LazySegtree<F>whereF: MapMonoid,{n: usize,size: usize,log: usize,d: Vec<<F::M as Monoid>::S>,lz: Vec<F::F>,}impl<F> LazySegtree<F>whereF: MapMonoid,{fn update(&mut self, k: usize) {self.d[k] = F::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);}fn all_apply(&mut self, k: usize, f: F::F) {self.d[k] = F::mapping(&f, &self.d[k]);if k < self.size {self.lz[k] = F::composition(&f, &self.lz[k]);}}fn push(&mut self, k: usize) {self.all_apply(2 * k, self.lz[k].clone());self.all_apply(2 * k + 1, self.lz[k].clone());self.lz[k] = F::identity_map();}}// TODO is it useful?use std::{fmt::{Debug, Error, Formatter, Write},ops::{Bound, RangeBounds},};impl<F> Debug for LazySegtree<F>whereF: MapMonoid,F::F: Debug,<F::M as Monoid>::S: Debug,{fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {for i in 0..self.log {for j in 0..1 << i {f.write_fmt(format_args!("{:?}[{:?}]\t",self.d[(1 << i) + j],self.lz[(1 << i) + j]))?;}f.write_char('\n')?;}for i in 0..self.size {f.write_fmt(format_args!("{:?}\t", self.d[self.size + i]))?;}Ok(())}}fn main() {std::thread::Builder::new().stack_size(128 * 1024 * 1024).spawn(|| Solver::default().solve()).unwrap().join().unwrap();}#[macro_export]macro_rules! input {() => {};(mut $var:ident: $t:tt, $($rest:tt)*) => {let mut $var = __input_inner!($t);input!($($rest)*)};($var:ident: $t:tt, $($rest:tt)*) => {let $var = __input_inner!($t);input!($($rest)*)};(mut $var:ident: $t:tt) => {let mut $var = __input_inner!($t);};($var:ident: $t:tt) => {let $var = __input_inner!($t);};}#[macro_export]macro_rules! __input_inner {(($($t:tt),*)) => {($(__input_inner!($t)),*)};([$t:tt; $n:expr]) => {(0..$n).map(|_| __input_inner!($t)).collect::<Vec<_>>()};([$t:tt]) => {{let n = __input_inner!(usize);(0..n).map(|_| __input_inner!($t)).collect::<Vec<_>>()}};(chars) => {__input_inner!(String).chars().collect::<Vec<_>>()};(bytes) => {__input_inner!(String).into_bytes()};(usize1) => {__input_inner!(usize) - 1};($t:ty) => {$crate::read::<$t>()};}#[macro_export]macro_rules! println {() => {$crate::write(|w| {use std::io::Write;std::writeln!(w).unwrap()})};($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::writeln!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! print {($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::write!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! flush {() => {$crate::write(|w| {use std::io::Write;w.flush().unwrap()})};}pub fn read<T>() -> TwhereT: std::str::FromStr,T::Err: std::fmt::Debug,{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());}STDIN.with(|r| {let mut r = r.borrow_mut();let mut s = vec![];loop {let buf = r.fill_buf().unwrap();if buf.is_empty() {break;}if let Some(i) = buf.iter().position(u8::is_ascii_whitespace) {s.extend_from_slice(&buf[..i]);r.consume(i + 1);if !s.is_empty() {break;}} else {s.extend_from_slice(buf);let n = buf.len();r.consume(n);}}std::str::from_utf8(&s).unwrap().parse().unwrap()})}pub fn write<F>(f: F)whereF: FnOnce(&mut std::io::BufWriter<std::io::StdoutLock>),{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> =RefCell::new(BufWriter::new(stdout().lock()));}STDOUT.with(|w| f(&mut w.borrow_mut()))}// trait Bound<T> {// fn lower_bound(&self, x: &T) -> usize;// fn upper_bound(&self, x: &T) -> usize;// }// impl<T: PartialOrd> Bound<T> for [T] {// fn lower_bound(&self, x: &T) -> usize {// let (mut low, mut high) = (0, self.len());// while low + 1 < high {// let mid = (low + high) / 2;// if self[mid] < *x {// low = mid;// } else {// high = mid;// }// }// if self[low] < *x {// low + 1// } else {// low// }// }// fn upper_bound(&self, x: &T) -> usize {// let (mut low, mut high) = (0, self.len());// while low + 1 < high {// let mid = (low + high) / 2;// if self[mid] <= *x {// low = mid;// } else {// high = mid;// }// }// if self[low] <= *x {// low + 1// } else {// low// }// }// }