結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー tipstar0125
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#![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 element
pub trait Zero {
/// The additive identity element
fn zero() -> Self;
}
/// Class that has multiplicative identity element
pub trait One {
/// The multiplicative identity element
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_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>
where
S: 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>
where
S: 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>
where
S: 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>
where
S: 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>
where
S: 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>
where
S: 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>
where
S: 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>::S
where
R: RangeBounds<usize>,
{
// Trivial optimization
if 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)
where
R: 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) -> usize
where
G: 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 {
// do
while 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) -> usize
where
G: 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 {
// do
r -= 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>
where
F: MapMonoid,
{
n: usize,
size: usize,
log: usize,
d: Vec<<F::M as Monoid>::S>,
lz: Vec<F::F>,
}
impl<F> LazySegtree<F>
where
F: 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>
where
F: 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>() -> T
where
T: 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)
where
F: 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
// }
// }
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0