#954279 (Rust) No.2650 [Cherry 6th Tune *] セイジャク

• 問題: No.2650 [Cherry 6th Tune *] セイジャク
• ユーザー: naut
• 提出日時: 2024-02-23 21:53:31
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 307 ms / 2,500 ms
• コード長: 6,371 bytes
• コンパイル時間: 15,175 ms
• コンパイル使用メモリ: 378,488 KB
• 実行使用メモリ: 30,848 KB
• 最終ジャッジ日時: 2024-05-06 00:35:40
• 合計ジャッジ時間: 26,535 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	55 ms; 9,088 KB
testcase_03	AC	30 ms; 5,888 KB
testcase_04	AC	221 ms; 22,400 KB
testcase_05	AC	151 ms; 17,408 KB
testcase_06	AC	67 ms; 9,856 KB
testcase_07	AC	166 ms; 18,944 KB
testcase_08	AC	42 ms; 7,680 KB
testcase_09	AC	292 ms; 30,080 KB
testcase_10	AC	291 ms; 30,336 KB
testcase_11	AC	304 ms; 30,208 KB
testcase_12	AC	303 ms; 30,208 KB
testcase_13	AC	296 ms; 30,208 KB
testcase_14	AC	307 ms; 30,208 KB
testcase_15	AC	302 ms; 30,208 KB
testcase_16	AC	263 ms; 29,696 KB
testcase_17	AC	265 ms; 29,696 KB
testcase_18	AC	257 ms; 29,696 KB
testcase_19	AC	257 ms; 29,696 KB
testcase_20	AC	261 ms; 29,824 KB
testcase_21	AC	262 ms; 29,824 KB
testcase_22	AC	268 ms; 29,824 KB
testcase_23	AC	205 ms; 30,336 KB
testcase_24	AC	205 ms; 30,464 KB
testcase_25	AC	204 ms; 30,336 KB
testcase_26	AC	200 ms; 30,336 KB
testcase_27	AC	200 ms; 30,336 KB
testcase_28	AC	208 ms; 30,336 KB
testcase_29	AC	204 ms; 30,464 KB
testcase_30	AC	217 ms; 28,672 KB
testcase_31	AC	209 ms; 30,848 KB
testcase_32	AC	89 ms; 11,520 KB

ソースコード

#![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())
            }
        }
    }
}