結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー naut3
提出日時 2024-02-23 21:53:31
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 289 ms / 2,500 ms
コード長 6,371 bytes
コンパイル時間 25,356 ms
コンパイル使用メモリ 396,584 KB
実行使用メモリ 30,848 KB
最終ジャッジ日時 2024-11-28 02:07:15
合計ジャッジ時間 36,474 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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

#![allow(non_snake_case, unused_imports, unused_must_use)]
use std::io::{self, prelude::*};
use std::str;
fn main() {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = Scanner::new(stdin.lock());
    let mut out = io::BufWriter::new(stdout.lock());
    macro_rules! input {
        ($T: ty) => {
            scan.token::<$T>()
        };
        ($T: ty, $N: expr) => {
            (0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>()
        };
    }
    let N = input!(usize);
    let A = input!(usize);
    let mut S = vec![A];
    let X = input!(usize, N);
    for &x in X.iter() {
        S.push(x);
    }
    let T = input!(usize);
    let mut LR = vec![];
    for _ in 0..T {
        let (l, r) = (input!(usize), input!(usize));
        LR.push((l, r));
        S.push(l);
        S.push(r);
    }
    let cc = CoordinateCompression::from(&S);
    let l = cc.values.len();
    let mut stree = dual_segment_tree::DualSegTree::new(l, |&x, &y| std::cmp::max(x, y), 0);
    for (i, &(l, r)) in LR.iter().enumerate() {
        let left = cc.lower_bound(&l).unwrap().1;
        let right = cc.upper_bound(&r).unwrap().1;
        stree.act_range(left..right, i + 1);
    }
    for i in 0..N {
        let p = cc.lower_bound(&X[i]).unwrap().1;
        let a = stree.get_point(p);
        if a == 0 {
            writeln!(out, "-1");
        } else {
            writeln!(out, "{}", a);
        }
    }
}
pub struct CoordinateCompression<T> {
    values: Vec<T>,
    order: std::collections::BTreeMap<T, usize>,
}
impl<T: Ord + Copy + std::fmt::Debug> CoordinateCompression<T> {
    pub fn from(values: &[T]) -> Self {
        let s = {
            let mut s = std::collections::BTreeSet::new();
            for &v in values {
                s.insert(v);
            }
            s
        };
        let values = s.iter().map(|&v| v).collect::<Vec<_>>();
        let mut order = std::collections::BTreeMap::new();
        for (i, &v) in values.iter().enumerate() {
            order.insert(v, i);
        }
        return Self {
            values: values,
            order: order,
        };
    }
    pub fn kth_value(&self, k: usize) -> T {
        return self.values[k];
    }
    pub fn get_order(&self, v: &T) -> usize {
        return *self.order.get(v).unwrap();
    }
    pub fn lower_bound(&self, v: &T) -> Option<(T, usize)> {
        let next_back_value = self.order.range(..=v).next_back();
        match next_back_value {
            Some((&rv, &i)) => return Some((rv, i)),
            None => return None,
        }
    }
    pub fn upper_bound(&self, v: &T) -> Option<(T, usize)> {
        let next_value = self.order.range(v..).nth(0);
        match next_value {
            Some((&rv, &i)) => {
                if rv != *v {
                    return Some((rv, i));
                } else {
                    let next_value2 = self.order.range(v..).nth(1);
                    match next_value2 {
                        Some((&rv2, &i2)) => {
                            assert_ne!(rv2, rv);
                            return Some((rv2, i2));
                        }
                        None => {
                            return None;
                        }
                    }
                }
            }
            None => return None,
        }
    }
    pub fn all_values(&self) -> std::slice::Iter<'_, T> {
        return self.values.iter();
    }
}
pub mod dual_segment_tree {
    pub struct DualSegTree<T> {
        size: usize,
        tree: Vec<T>,
        op: fn(&T, &T) -> T,
    }
    impl<T: Clone + Copy> DualSegTree<T> {
        /// self = [id; size], self.op = op
        pub fn new(size: usize, op: fn(&T, &T) -> T, id: T) -> Self {
            return Self {
                size: size,
                tree: vec![id; 2 * size],
                op: op,
            };
        }
        /// return self[point]
        pub fn get_point(&self, mut point: usize) -> T {
            point += self.size;
            let mut ret = self.tree[point];
            while point > 1 {
                point >>= 1;
                ret = (self.op)(&ret, &self.tree[point]);
            }
            return ret;
        }
        /// for each i ∈ [left, right), self[i] <- a ○ self[i]
        pub fn act(&mut self, mut left: usize, mut right: usize, a: T) {
            left += self.size;
            right += self.size;
            while left < right {
                if left & 1 == 1 {
                    self.tree[left] = (self.op)(&self.tree[left], &a);
                    left += 1;
                }
                if right & 1 == 1 {
                    right -= 1;
                    self.tree[right] = (self.op)(&self.tree[right], &a);
                }
                left >>= 1;
                right >>= 1;
            }
        }
        /// for each i ∈ range, self[i] <- a ○ self[i]
        pub fn act_range<R: std::ops::RangeBounds<usize>>(&mut self, range: R, a: T) {
            let left = match range.start_bound() {
                std::ops::Bound::Included(&l) => l,
                std::ops::Bound::Excluded(&l) => l + 1,
                std::ops::Bound::Unbounded => 0,
            };
            let right = match range.end_bound() {
                std::ops::Bound::Included(&r) => r + 1,
                std::ops::Bound::Excluded(&r) => r,
                std::ops::Bound::Unbounded => self.size,
            };
            return self.act(left, right, a);
        }
    }
}
struct Scanner<R> {
    reader: R,
    buf_str: Vec<u8>,
    buf_iter: str::SplitWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
    fn new(reader: R) -> Self {
        Self {
            reader,
            buf_str: vec![],
            buf_iter: "".split_whitespace(),
        }
    }
    fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buf_iter.next() {
                return token.parse().ok().expect("Failed parse");
            }
            self.buf_str.clear();
            self.reader
                .read_until(b'\n', &mut self.buf_str)
                .expect("Failed read");
            self.buf_iter = unsafe {
                let slice = str::from_utf8_unchecked(&self.buf_str);
                std::mem::transmute(slice.split_whitespace())
            }
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0