use std::collections::*; use std::ops::Bound::*; fn main() { let v = read_vec::(); let (n, a, b) = (v[0] as usize, v[1], v[2]); let x = read_vec::() .into_iter() .enumerate() .map(|x| (x.1, x.0)) .collect::>(); let mut edges = vec![std::usize::MAX; n]; for &xnum in &x { let mut left = x.range((Included((xnum.0 + a, 0)), Included((xnum.0 + b, n)))); if let Some(left) = left.next() { let left = left.1; let right = x .range((Included((xnum.0 + a, 0)), Included((xnum.0 + b, n)))) .rev() .next() .unwrap() .1; edges[xnum.1] = right; if edges[left] == std::usize::MAX { for i in left..right { edges[i] = right; } } else { for i in edges[left]..right { edges[i] = right; } } } } let mut uft = UnionFindTree::new(n); for (i, to) in edges.into_iter().enumerate() { if to == std::usize::MAX { continue; } uft.unite(i, to); } for i in 0..n { println!("{}", uft.get_size(i)); } } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Debug, Clone)] struct UnionFindTree { parent: Vec, size: Vec, height: Vec, } impl UnionFindTree { fn new(n: usize) -> UnionFindTree { UnionFindTree { parent: vec![-1; n], size: vec![1usize; n], height: vec![0u64; n], } } fn find(&mut self, index: usize) -> usize { if self.parent[index] == -1 { return index; } let idx = self.parent[index] as usize; let ret = self.find(idx); self.parent[index] = ret as isize; ret } fn get_size(&mut self, x: usize) -> usize { let idx = self.find(x); self.size[idx] } fn unite(&mut self, index0: usize, index1: usize) -> bool { let a = self.find(index0); let b = self.find(index1); if a == b { false } else { if self.height[a] > self.height[b] { self.parent[b] = a as isize; self.size[a] += self.size[b]; } else if self.height[a] < self.height[b] { self.parent[a] = b as isize; self.size[b] += self.size[a]; } else { self.parent[b] = a as isize; self.size[a] += self.size[b]; self.height[a] += 1; } true } } }