Submission #62805776

---

Source Code Expand

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        q: usize,
        a: [u64; n],
        queries: [(Usize1, u64); q],
    }

    let mut ans = vec![0; q];
    let mut qi = 0;
    let indicates = (0..q).sorted_unstable_by_key(|i| queries[*i].0).collect_vec();

    let mut dp = vec![INF; n];
    let mut mv = vec![INF; n];

    for i in 0..n {
        let idx = dp.lower_bound(a[i]);
        dp[idx] = a[i];
        mv[idx] = mv[idx].min(a[i]);

        while qi < q && queries[indicates[qi]].0 == i {
            let j = mv.lower_bound(queries[indicates[qi]].1);
            ans[indicates[qi]] = if j < n && mv[j] == queries[indicates[qi]].1 { j + 1 } else { j };
            qi += 1;
        }
    }
    println!("{}", ans.iter().join("\n"));
}
pub static INF: u64 = 1e18 as u64;
pub static DI: &[usize] = &[0, !0, 0, 1, !0, 1, !0, 1];
pub static DJ: &[usize] = &[!0, 0, 1, 0, !0, !0, 1, 1];
pub static DC: &[char] = &['L', 'U', 'R', 'D'];
pub trait VecLibs<T: std::cmp::Ord> {
    fn lower_bound(&self, elm: T) -> usize;
    fn upper_bound(&self, elm: T) -> usize;
}

impl<T: std::cmp::Ord> VecLibs<T> for Vec<T> {
    fn lower_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] < elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    fn upper_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] <= elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }
}

Submission Info

Judge Result