#![allow(non_snake_case, unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: usize, K: isize, X: [isize; N], } let mut pos = std::collections::BTreeMap::default(); for i in 0..N { pos.insert(X[i], i); } let mut dp = SegmentTree::new(N, |&x, &y| std::cmp::max(x, y), 1); for i in 0..N { let l = pos.range(..=(X[i] - K)).next_back(); match l { Some((_, &p)) => { let m = dp.prod(..=p); dp.insert(i, m + 1); } None => (), } } let ans = dp.prod(..); println!("{}", ans); } pub struct SegmentTree { size: usize, tree: Vec, op: fn(&M, &M) -> M, id: M, } impl SegmentTree { /// self = [id; size], self.op = op, self.id = id pub fn new(size: usize, op: fn(&M, &M) -> M, id: M) -> Self { return Self { size: size, tree: vec![id; 2 * size], op: op, id: id, }; } /// self = arr, self.op = op, self.id = id pub fn from(arr: &[M], op: fn(&M, &M) -> M, id: M) -> Self { let size = arr.len(); let mut tree = vec![id; 2 * size]; for i in 0..size { tree[i + size] = arr[i]; assert!(op(&id, &arr[i]) == arr[i]); } for i in (1..size).rev() { tree[i] = op(&tree[i << 1], &tree[i << 1 | 1]); } return Self { size: size, tree: tree, op: op, id: id, }; } /// self[pos] <- value pub fn insert(&mut self, mut pos: usize, value: M) -> () { pos += self.size; self.tree[pos] = value; while pos > 1 { pos >>= 1; self.tree[pos] = (self.op)(&self.tree[pos << 1], &self.tree[pos << 1 | 1]); } } /// return self[pos] pub fn get_point(&self, pos: usize) -> M { return self[pos]; } /// return Π_{i ∈ [left, right)} self[i] pub fn get(&self, left: usize, right: usize) -> M { let (mut l, mut r) = (left + self.size, right + self.size); let (mut vl, mut vr) = (self.id, self.id); while l < r { if l & 1 == 1 { vl = (self.op)(&vl, &self.tree[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = (self.op)(&self.tree[r], &vr); } l >>= 1; r >>= 1; } return (self.op)(&vl, &vr); } /// return Π_{i ∈ range} self[i] pub fn prod>(&self, range: R) -> M { 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.get(left, right); } } impl std::ops::Index for SegmentTree { type Output = M; fn index(&self, index: usize) -> &Self::Output { &self.tree[index + self.size] } } impl std::fmt::Display for SegmentTree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!( f, "{}", self.tree[self.size..] .iter() .map(|x| x.to_string()) .collect::>() .join(" ") ) } }