結果
| 問題 | No.3446 Range Adjacent Differences |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-02-18 21:41:15 |
| 言語 | Rust (1.93.0 + proconio + num + itertools) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,449 bytes |
| 記録 | |
| コンパイル時間 | 3,047 ms |
| コンパイル使用メモリ | 225,156 KB |
| 実行使用メモリ | 19,840 KB |
| 最終ジャッジ日時 | 2026-02-18 21:41:26 |
| 合計ジャッジ時間 | 7,738 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 25 |
コンパイルメッセージ
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>; | ^^^^^
ソースコード
// 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 = HashMap::new();
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 = hist.entry(d).or_insert(0);
*po -= 1;
if *po == 0 {
hist.remove(&d);
c.remove(d);
}
}
if let Some(p) = set.prev(pos) {
let d = a[i] - a[z[p]];
let po = hist.entry(d).or_insert(0);
*po += 1;
if *po == 1 {
c.insert(d);
}
}
if let Some(p) = set.next(pos) {
let d = a[z[p]] - a[i];
let po = hist.entry(d).or_insert(0);
*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 = hist.entry(d).or_insert(0);
*po -= 1;
if *po == 0 {
hist.remove(&d);
c.remove(d);
}
}
if let Some(p) = set.next(pos) {
let d = a[z[p]] - a[i];
let po = hist.entry(d).or_insert(0);
*po -= 1;
if *po == 0 {
hist.remove(&d);
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 = hist.entry(d).or_insert(0);
*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
}
}