#1148471 (Rust) No.3446 Range Adjacent Differences

• 問題: No.3446 Range Adjacent Differences
• ユーザー: akakimidori
• 提出日時: 2026-02-18 21:43:02
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,632 ms / 2,200 ms
• コード長: 8,689 bytes
• コンパイル時間: 3,409 ms
• コンパイル使用メモリ: 223,504 KB
• 実行使用メモリ: 24,760 KB
• 最終ジャッジ日時: 2026-02-18 21:43:41
• 合計ジャッジ時間: 31,389 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 26

コンパイルメッセージ

warning: type alias `Map` is never used
 --> src/main.rs:8:6
  |
8 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Set` is never used
 --> src/main.rs:9:6
  |
9 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
  --> src/main.rs:10:6
   |
10 | type Deque<T> = VecDeque<T>;
   |      ^^^^^

warning: function `rand_memory` is never used
   --> src/main.rs:298:4
    |
298 | fn rand_memory() -> usize {
    |    ^^^^^^^^^^^

warning: function `rand` is never used
   --> src/main.rs:302:4
    |
302 | fn rand() -> usize {
    |    ^^^^

warning: function `shuffle` is never used
   --> src/main.rs:315:4
    |
315 | fn shuffle<T>(a: &mut [T]) {
    |    ^^^^^^^

ソースコード

// Mo?
// 数列Aが全て異なるとしておく
// mapへの操作が大量に発生して辛いような

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        ask: [(usize1, usize, usize, char); q],
    }
    let batch = 400;
    let mut ord = (0..q).collect::<Vec<_>>();
    ord.sort_by_key(|x| {
        let (l, r, _, _) = ask[*x];
        let q = l / batch;
        if q % 2 == 0 {
            (q, r)
        } else {
            (q, !r)
        }
    });
    let mut z = (0..n).collect::<Vec<_>>();
    z.sort_by_key(|z| a[*z]);
    let mut iz = vec![0; n];
    for i in 0..n {
        iz[z[i]] = i;
    }
    let mut set = FastSet::new(n);
    let mut hist = vec![0i32; 10000000];
    let mut c = FastSet::new(10000000);
    let mut ans = vec![-1; q];
    let mut s = 0;
    let mut t = 0;
    for k in ord {
        let (l, r, x, op) = ask[k];
        for i in (l..s).chain(t..r) {
            let pos = iz[i];
            if let (Some(p), Some(q)) = (set.prev(pos), set.next(pos)) {
                let d = a[z[q]] - a[z[p]];
                let po = &mut hist[d];
                *po -= 1;
                if *po == 0 {
                    c.remove(d);
                }
            }
            if let Some(p) = set.prev(pos) {
                let d = a[i] - a[z[p]];
                let po = &mut hist[d];
                *po += 1;
                if *po == 1 {
                    c.insert(d);
                }
            }
            if let Some(p) = set.next(pos) {
                let d = a[z[p]] - a[i];
                let po = &mut hist[d];
                *po += 1;
                if *po == 1 {
                    c.insert(d);
                }
            }
            set.insert(pos);
        }
        for i in (s..l).chain(r..t) {
            let pos = iz[i];
            set.remove(pos);
            if let Some(p) = set.prev(pos) {
                let d = a[i] - a[z[p]];
                let po = &mut hist[d];
                *po -= 1;
                if *po == 0 {
                    c.remove(d);
                }
            }
            if let Some(p) = set.next(pos) {
                let d = a[z[p]] - a[i];
                let po = &mut hist[d];
                *po -= 1;
                if *po == 0 {
                    c.remove(d);
                }
            }
            if let (Some(p), Some(q)) = (set.prev(pos), set.next(pos)) {
                let d = a[z[q]] - a[z[p]];
                let po = &mut hist[d];
                *po += 1;
                if *po == 1 {
                    c.insert(d);
                }
            }
        }
        s = l;
        t = r;
        if op == 'L' {
            if let Some(q) = c.prev(x) {
                ans[k] = q as i32;
            }
        } else {
            if let Some(q) = c.next(x) {
                ans[k] = q as i32;
            }
        }
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for a in ans {
        writeln!(out, "{a}").ok();
    }
}

fn main() {
    run();
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
pub struct FastSet {
    size: usize,
    seg: Vec<Vec<usize>>,
}

impl FastSet {
    pub fn build<I>(size: usize, init: I) -> Self
    where
        I: Iterator<Item = usize>
    {
        assert!(size > 0);
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        let mut data = vec![0; (n + w - 1) / w];
        for x in init {
            assert!(x < size);
            data[x / w] |= 1 << (x % w);
        }
        seg.push(data);
        while n > 1 {
            n = (n + w - 1) / w;
            let d = seg.last().unwrap().chunks(w).map(|a| {
                a.iter().enumerate().filter(|p| *p.1 > 0).fold(0, |s, a| s | (1 << a.0))
            }).collect::<Vec<_>>();
            seg.push(d);
        }
        Self { size, seg }
    }
    pub fn new(size: usize) -> Self {
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        while {
            let m = (n + w - 1) / w;
            seg.push(vec![0; m]);
            n = m;
            n > 1
        } {}
        Self { size, seg }
    }
    pub fn insert(&mut self, mut x: usize) -> bool {
        assert!(x < self.size, "{x} {}", self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) == 1 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] |= 1 << (x % w);
            x /= w;
        }
        true
    }
    pub fn remove(&mut self, mut x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) == 0 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] &= !(1 << (x % w));
            if seg[x / w] != 0 {
                break;
            }
            x /= w;
        }
        true
    }
    pub fn contains(&self, x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        self.seg[0][x / w] >> (x % w) & 1 == 1
    }
    pub fn next(&self, mut x: usize) -> Option<usize> {
        if x >= self.size {
            return None;
        }
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            if x / w == s.len() {
                return None;
            }
            if s[x / w] >> (x % w) == 0 {
                x = x / w + 1;
                continue;
            }
            let k = (s[x / w] >> (x % w)).trailing_zeros() as usize;
            x += k;
            for seg in seg[..i].iter().rev() {
                let k = seg[x].trailing_zeros() as usize;
                x = w * x + k;
            }
            return Some(x)
        }
        None
    }
    pub fn prev(&self, mut x: usize) -> Option<usize> {
        x = x.min(self.size - 1);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            let d = s[x / w] << (w - 1 - x % w);
            if d == 0 {
                if x < w {
                    break;
                }
                x = x / w - 1;
                continue;
            }
            let k = d.leading_zeros() as usize;
            x -= k;
            for seg in seg[..i].iter().rev() {
                let k = w - 1 - seg[x].leading_zeros() as usize;
                x = w * x + k;
            }
            return Some(x);
        }
        None
    }
}
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}