結果
| 問題 | No.3446 Range Adjacent Differences |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-02-18 22:49:51 |
| 言語 | Rust (1.93.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 1,164 ms / 2,200 ms |
| コード長 | 6,599 bytes |
| 記録 | |
| コンパイル時間 | 2,641 ms |
| コンパイル使用メモリ | 217,736 KB |
| 実行使用メモリ | 19,668 KB |
| 最終ジャッジ日時 | 2026-02-18 22:50:12 |
| 合計ジャッジ時間 | 19,343 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
use proconio::marker::*;
use proconio::*;
#[fastout]
fn run() {
input! {
n: usize,
q: usize,
a: [usize; n],
ask: [(Usize1, usize, usize, char); q],
}
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 za = vec![0; n];
for i in 0..n {
za[i] = a[z[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;
let batch = (1..).find(|&i| i * i > q).unwrap();
let mut ord = (0..q).collect::<Vec<_>>();
ord.sort_by_key(|x| ask[*x].0);
for (i, ord) in ord.chunks_mut(batch).enumerate() {
ord.sort_by_key(|x| ask[*x].1);
if i % 2 == 1 {
ord.reverse();
}
for &k in ord.iter() {
let (l, r, x, op) = ask[k];
for i in (l..s).chain(t..r) {
let pos = iz[i];
let (p, q) = (set.prev(pos), set.next(pos));
if let (Some(p), Some(q)) = (p, q) {
let d = za[q] - za[p];
remove(d, &mut hist, &mut c);
}
if let Some(p) = p {
let d = a[i] - za[p];
insert(d, &mut hist, &mut c);
}
if let Some(p) = q {
let d = za[p] - a[i];
insert(d, &mut hist, &mut c);
}
set.insert(pos);
}
for i in (s..l).chain(r..t) {
let pos = iz[i];
set.remove(pos);
let (p, q) = (set.prev(pos), set.next(pos));
if let Some(p) = p {
let d = a[i] - za[p];
remove(d, &mut hist, &mut c);
}
if let Some(p) = q {
let d = za[p] - a[i];
remove(d, &mut hist, &mut c);
}
if let (Some(p), Some(q)) = (p, q) {
let d = za[q] - za[p];
insert(d, &mut hist, &mut c);
}
}
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;
}
}
}
}
for a in ans {
println!("{}", a);
}
}
fn insert(d: usize, hist: &mut [i32], c: &mut FastSet) {
hist[d] += 1;
if hist[d] == 1 {
c.insert(d);
}
}
fn remove(d: usize, hist: &mut [i32], c: &mut FastSet) {
hist[d] -= 1;
if hist[d] == 0 {
c.remove(d);
}
}
fn main() {
run();
}
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);
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) & 1 == 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;
}
let d = s[x / w] >> (x % w);
if d == 0 {
x = x / w + 1;
continue;
}
x += d.trailing_zeros() as usize;
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;
}
x -= d.leading_zeros() as usize;
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
}
}