提出 #62785883

---

ソースコード 拡げる

use proconio::{input, marker::Usize1};
use riff::SliceBinarySearch;

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [u32; n],
        raw_queries: [(Usize1, u32); q],
    }
    let mut queries = vec![vec![]; n];
    for (i, &(r, _)) in raw_queries.iter().enumerate() {
        queries[r].push(i);
    }
    let mut dp = vec![];
    let mut ans = vec![usize::MAX; q];
    for (i, &x) in a.iter().enumerate() {
        let lb = dp.lower_bound(&x);
        if dp.len() == lb {
            dp.push(x);
        } else {
            dp[lb] = x;
        }
        for &j in &queries[i] {
            let (_, x) = raw_queries[j];
            ans[j] = dp.upper_bound(&x);
        }
    }
    for &ans in &ans {
        println!("{ans}");
    }
}

// riff {{{
// https://ngtkana.github.io/ac-adapter-rs/riff/index.html

#[allow(dead_code)]
mod riff {
    mod bitmask_iterators {
        use super::numeric_traits::Unsigned;
        pub fn bitmask_combinations<T: Unsigned>(n: u32, k: u32) -> BitmaskCombinations<T> {
            assert!(k < T::bit_length() && k < T::bit_length());
            BitmaskCombinations {
                n,
                bs: (T::ONE << k) - T::ONE,
            }
        }
        #[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
        pub struct BitmaskCombinations<T> {
            n: u32,
            bs: T,
        }
        impl<T: Unsigned> Iterator for BitmaskCombinations<T> {
            type Item = T;
            fn next(&mut self) -> Option<Self::Item> {
                if (T::ONE << self.n) <= self.bs {
                    return None;
                }
                let res = Some(self.bs);
                self.bs = if self.bs == T::ZERO {
                    T::ONE << self.n
                } else {
                    let x = self.bs & self.bs.wrapping_neg();
                    let y = self.bs + x;
                    (((self.bs & !y) / x) >> 1) | y
                };
                res
            }
        }
        pub fn bitmask_subsets<T: Unsigned>(bs: T) -> BitmaskSubsets<T> {
            BitmaskSubsets {
                bs,
                full: bs,
                finished: false,
            }
        }
        #[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
        pub struct BitmaskSubsets<T> {
            bs: T,
            full: T,
            finished: bool,
        }
        impl<T: Unsigned> Iterator for BitmaskSubsets<T> {
            type Item = T;
            fn next(&mut self) -> Option<Self::Item> {
                if self.finished {
                    return None;
                }
                let res = Some(self.bs ^ self.full);
                if self.bs == T::ZERO {
                    self.finished = true;
                } else {
                    self.bs -= T::ONE;
                    self.bs &= self.full;
                }
                res
            }
        }
    }
    mod bitmask_operations {
        use crate::riff::Unsigned;
        pub fn i2powm1<T: Unsigned>(n: u32) -> T {
            if n == T::bit_length() {
                T::MAX
            } else {
                (T::ONE << n) - T::ONE
            }
        }
    }
    mod change_min_max {
        pub trait ChangeMinMax: PartialOrd + Sized {
            fn change_min(&mut self, rhs: Self) {
                if *self > rhs {
                    *self = rhs
                }
            }
            fn change_max(&mut self, rhs: Self) {
                if *self < rhs {
                    *self = rhs
                }
            }
        }
        impl<T: PartialOrd + Sized> ChangeMinMax for T {}
    }
    mod numeric_traits {
        use std::fmt::Debug;
        use std::mem::size_of;
        use std::ops::Add;
        use std::ops::AddAssign;
        use std::ops::BitAnd;
        use std::ops::BitAndAssign;
        use std::ops::BitOr;
        use std::ops::BitOrAssign;
        use std::ops::BitXor;
        use std::ops::BitXorAssign;
        use std::ops::Div;
        use std::ops::DivAssign;
        use std::ops::Mul;
        use std::ops::MulAssign;
        use std::ops::Not;
        use std::ops::Shl;
        use std::ops::ShlAssign;
        use std::ops::Shr;
        use std::ops::ShrAssign;
        use std::ops::Sub;
        use std::ops::SubAssign;
        pub trait Unsigned:
            Sized
            + PartialEq
            + PartialOrd
            + Debug
            + Clone
            + Copy
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + BitAnd<Output = Self>
            + BitAndAssign
            + BitOr<Output = Self>
            + BitOrAssign
            + BitXor<Output = Self>
            + BitXorAssign
            + Shl<u32, Output = Self>
            + ShlAssign<u32>
            + Shr<u32, Output = Self>
            + ShrAssign<u32>
            + Not<Output = Self>
        {
            const BITS: u32;
            const MAX: Self;
            const ZERO: Self;
            const ONE: Self;
            fn wrapping_neg(self) -> Self;
            fn bit_length() -> u32 {
                size_of::<Self>() as u32 * 8
            }
        }
        macro_rules! impl_unsigned {
            ($($T:ty),* $(,)?) => {$(
                impl Unsigned for $T {
                    const BITS: u32 = <$T>::BITS;
                    const MAX: Self = <$T>::MAX;
                    const ZERO: Self = 0;
                    const ONE: Self = 1;
                    fn wrapping_neg(self) -> Self { self.wrapping_neg() }
                }
            )*}
        }
        impl_unsigned! { usize, u8, u16, u32, u64, u128 }
    }
    mod pop_if {
        use std::collections::BinaryHeap;
        pub trait PopIf {
            type Value;
            fn pop_if<F>(&mut self, f: F) -> Option<Self::Value>
            where
                F: FnOnce(&mut Self::Value) -> bool;
        }
        impl<T> PopIf for Vec<T> {
            type Value = T;
            fn pop_if<F>(&mut self, f: F) -> Option<Self::Value>
            where
                F: FnOnce(&mut Self::Value) -> bool,
            {
                if f(self.last_mut()?) {
                    self.pop()
                } else {
                    None
                }
            }
        }
        impl<T: Ord> PopIf for BinaryHeap<T> {
            type Value = T;
            fn pop_if<F>(&mut self, f: F) -> Option<Self::Value>
            where
                F: FnOnce(&mut Self::Value) -> bool,
            {
                if f(&mut *self.peek_mut()?) {
                    self.pop()
                } else {
                    None
                }
            }
        }
    }
    mod slice_accum {
        use std::ops::AddAssign;
        use std::ops::SubAssign;
        pub trait SliceAccum<T> {
            fn for_each_forward<F>(&mut self, f: F)
            where
                F: FnMut(&mut T, &mut T);
            fn for_each_backward<F>(&mut self, f: F)
            where
                F: FnMut(&mut T, &mut T);
            fn prefix_sum(&mut self)
            where
                for<'a> T: AddAssign<&'a T>,
            {
                self.for_each_forward(|x, y| *x += y);
            }
            fn prefix_sum_inv(&mut self)
            where
                for<'a> T: SubAssign<&'a T>,
            {
                self.for_each_backward(|x, y| *y -= x);
            }
            fn suffix_sum(&mut self)
            where
                for<'a> T: AddAssign<&'a T>,
            {
                self.for_each_backward(|x, y| *x += y);
            }
            fn suffix_sum_inv(&mut self)
            where
                for<'a> T: SubAssign<&'a T>,
            {
                self.for_each_forward(|x, y| *y -= x);
            }
        }
        impl<T> SliceAccum<T> for [T] {
            fn for_each_forward<F>(&mut self, mut f: F)
            where
                F: FnMut(&mut T, &mut T),
            {
                for i in 1..self.len() {
                    let (left, right) = self.split_at_mut(i);
                    f(&mut right[0], &mut left[i - 1]);
                }
            }
            fn for_each_backward<F>(&mut self, mut f: F)
            where
                F: FnMut(&mut T, &mut T),
            {
                for i in (1..self.len()).rev() {
                    let (left, right) = self.split_at_mut(i);
                    f(&mut left[i - 1], &mut right[0]);
                }
            }
        }
    }
    mod slice_binary_search {
        use std::cmp::Ordering;
        use std::cmp::Ordering::Equal;
        use std::cmp::Ordering::Greater;
        use std::cmp::Ordering::Less;
        pub trait SliceBinarySearch<T> {
            fn partition_point<F: FnMut(&T) -> bool>(&self, pred: F) -> usize;
            fn partition_point_value<F: FnMut(&T) -> bool>(&self, pred: F) -> Option<&T>;
            fn lower_bound_by<F: FnMut(&T) -> Ordering>(&self, mut f: F) -> usize {
                self.partition_point(|x| f(x) < Equal)
            }
            fn upper_bound_by<F: FnMut(&T) -> Ordering>(&self, mut f: F) -> usize {
                self.partition_point(|x| f(x) <= Equal)
            }
            fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, mut f: F) -> usize {
                self.lower_bound_by(|x| f(x).cmp(b))
            }
            fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, mut f: F) -> usize {
                self.upper_bound_by(|x| f(x).cmp(b))
            }
            fn lower_bound(&self, x: &T) -> usize
            where
                T: Ord,
            {
                self.lower_bound_by(|p| p.cmp(x))
            }
            fn upper_bound(&self, x: &T) -> usize
            where
                T: Ord,
            {
                self.upper_bound_by(|p| p.cmp(x))
            }
            fn lower_bound_value_by<F: FnMut(&T) -> Ordering>(&self, mut f: F) -> Option<&T> {
                self.partition_point_value(|x| f(x) < Equal)
            }
            fn upper_bound_value_by<F: FnMut(&T) -> Ordering>(&self, mut f: F) -> Option<&T> {
                self.partition_point_value(|x| f(x) <= Equal)
            }
            fn lower_bound_value_by_key<B: Ord, F: FnMut(&T) -> B>(
                &self,
                b: &B,
                mut f: F,
            ) -> Option<&T> {
                self.lower_bound_value_by(|x| f(x).cmp(b))
            }
            fn upper_bound_value_by_key<B: Ord, F: FnMut(&T) -> B>(
                &self,
                b: &B,
                mut f: F,
            ) -> Option<&T> {
                self.upper_bound_value_by(|x| f(x).cmp(b))
            }
            fn lower_bound_value(&self, x: &T) -> Option<&T>
            where
                T: Ord,
            {
                self.lower_bound_value_by(|p| p.cmp(x))
            }
            fn upper_bound_value(&self, x: &T) -> Option<&T>
            where
                T: Ord,
            {
                self.upper_bound_value_by(|p| p.cmp(x))
            }
        }
        impl<T> SliceBinarySearch<T> for [T] {
            fn partition_point<F: FnMut(&T) -> bool>(&self, mut pred: F) -> usize {
                self.binary_search_by(|x| if pred(x) { Less } else { Greater })
                    .unwrap_err()
            }
            fn partition_point_value<F: FnMut(&T) -> bool>(&self, pred: F) -> Option<&T> {
                self.get(self.partition_point(pred))
            }
        }
    }
    mod slice_chunks {
        pub trait SliceChunks {
            type Item;
            fn chunk_by<F>(&self, f: F) -> SliceChunkBy<'_, Self::Item, F>
            where
                F: FnMut(&Self::Item, &Self::Item) -> bool;
        }
        impl<T> SliceChunks for [T] {
            type Item = T;
            fn chunk_by<F>(&self, f: F) -> SliceChunkBy<'_, Self::Item, F>
            where
                F: FnMut(&Self::Item, &Self::Item) -> bool,
            {
                SliceChunkBy { a: self, f }
            }
        }
        pub struct SliceChunkBy<'a, T, F> {
            a: &'a [T],
            f: F,
        }
        impl<'a, T, F> Iterator for SliceChunkBy<'a, T, F>
        where
            F: FnMut(&T, &T) -> bool,
        {
            type Item = &'a [T];
            fn next(&mut self) -> Option<Self::Item> {
                let Self { a, f } = self;
                if a.is_empty() {
                    return None;
                }
                let mut end = 1;
                while end < a.len() && f(&a[end - 1], &a[end]) {
                    end += 1;
                }
                let (prefix, rest) = a.split_at(end);
                self.a = rest;
                Some(prefix)
            }
        }
    }
    pub use bitmask_iterators::bitmask_combinations;
    pub use bitmask_iterators::bitmask_subsets;
    pub use bitmask_operations::i2powm1;
    pub use change_min_max::ChangeMinMax;
    pub use numeric_traits::Unsigned;
    pub use pop_if::PopIf;
    pub use slice_accum::SliceAccum;
    pub use slice_binary_search::SliceBinarySearch;
    pub use slice_chunks::SliceChunks;
}
// }}}

提出情報

ジャッジ結果