結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-03-05 16:57:31 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 16,296 bytes |
コンパイル時間 | 14,919 ms |
コンパイル使用メモリ | 388,064 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 23:28:18 |
合計ジャッジ時間 | 14,864 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
use input::input_array;use input::input_vec;use std::cmp::Ordering;use veb::VebMap;fn main() {let [n, _m] = input_array::<usize, 2>();let mut a = input_vec::<usize>();for x in &mut a {*x -= 1;}let mut dist = VebMap::new(n);dist.insert(0, 0);dist.insert(n - 1, n - 1);macro_rules! lerp {($x:expr) => {lerp(&mut dist, $x)};}for &x1 in a.iter().rev() {let x2 = x1 + 1;if x1 != 0 {lerp!(x1 - 1);}let y1 = lerp!(x1);let y2 = lerp!(x2);if x2 != n - 1 {lerp!(x2 + 1);}match y1.cmp(&y2) {Ordering::Equal => {}Ordering::Less => {if x1 == 0 || lerp!(x1 - 1) >= lerp!(x1) {*dist.get_mut(x1).unwrap() += 1;}if let Some((mut x3, mut y3)) = dist.succ(x2).map(|(x, &y)| (x, y)).filter(|&(x, y)| y == y2 + x - x2){while let Some((x, y)) = dist.succ(x3).map(|(x, &y)| (x, y)).filter(|&(x, y)| y == y3 + x - x3){dist.remove(x3);x3 = x;y3 = y;}dist.insert(x3, y3 - 1);}dist.insert(x2, y2 - 1);}Ordering::Greater => {if x2 == n - 1 || lerp!(x2 + 1) >= lerp!(x2) {*dist.get_mut(x2).unwrap() += 1;}if let Some((mut x0, mut y0)) = dist.pred(x1).map(|(x, &y)| (x, y)).filter(|&(x, y)| y == y1 + x1 - x){while let Some((x, y)) = dist.pred(x0).map(|(x, &y)| (x, y)).filter(|&(x, y)| y == y0 + x0 - x){dist.remove(x0);x0 = x;y0 = y;}dist.insert(x0, y0 - 1);}dist.insert(x1, y1 - 1);}}}println!("{}",(1..n).map(|i| lerp!(i)).map(|x| x.to_string()).collect::<Vec<_>>().join(" "));}fn lerp(map: &mut VebMap<usize>, x: usize) -> usize {if let Some(&y) = map.get(x) {return y;}let (x0, &y0) = map.pred(x).unwrap();let (x1, &y1) = map.succ(x).unwrap();assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);let y = y0 + (x - x0) * (y1 - y0) / (x1 - x0);map.insert(x, y);y}// input {{{#[allow(dead_code)]mod input {use std::cell::Cell;use std::convert::TryFrom;use std::io::stdin;use std::io::BufRead;use std::io::BufReader;use std::io::Lines;use std::io::Stdin;use std::str::FromStr;use std::sync::Mutex;use std::sync::Once;type Server = Mutex<Lines<BufReader<Stdin>>>;static ONCE: Once = Once::new();pub struct Lazy(Cell<Option<Server>>);unsafe impl Sync for Lazy {}fn line() -> String {static SYNCER: Lazy = Lazy(Cell::new(None));ONCE.call_once(|| {SYNCER.0.set(Some(Mutex::new(BufReader::new(stdin()).lines())));});unsafe {(*SYNCER.0.as_ptr()).as_ref().unwrap().lock().unwrap().next().unwrap().unwrap()}}pub trait ForceFromStr: FromStr {fn force_from_str(s: &str) -> Self;}impl<T, E> ForceFromStr for TwhereT: FromStr<Err = E>,E: std::fmt::Debug,{fn force_from_str(s: &str) -> Self {s.parse().unwrap()}}pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]whereT: std::fmt::Debug,{<[_; N]>::try_from(input_vec()).unwrap()}pub fn input_vec<T: ForceFromStr>() -> Vec<T> {line().split_whitespace().map(T::force_from_str).collect::<Vec<_>>()}pub fn input<T: ForceFromStr>() -> T {T::force_from_str(&line())}}// }}}// veb {{{#[allow(dead_code)]mod veb {use std::collections::HashMap;macro_rules! multi_or_else {($e:expr, $($f:expr),+) => {$e.or_else(|| multi_or_else!($($f),+))};($e:expr) => {$e};}pub struct VebMap<V> {veb: VebSet,map: HashMap<usize, V>,}impl<V> VebMap<V> {pub fn new(n: usize) -> Self {Self {veb: VebSet::new(n),map: HashMap::new(),}}pub fn insert(&mut self, i: usize, v: V) -> Option<V> {self.veb.insert(i);self.map.insert(i, v)}pub fn remove(&mut self, i: usize) -> Option<V> {self.veb.remove(i);self.map.remove(&i)}pub fn get(&self, i: usize) -> Option<&V> {self.map.get(&i)}pub fn get_mut(&mut self, i: usize) -> Option<&mut V> {self.map.get_mut(&i)}pub fn min_key(&self) -> Option<usize> {self.veb.min()}pub fn min_value(&self) -> Option<&V> {self.veb.min().and_then(|i| self.map.get(&i))}pub fn min(&self) -> Option<(usize, &V)> {self.veb.min().and_then(|i| self.map.get(&i).map(|v| (i, v)))}pub fn max_key(&self) -> Option<usize> {self.veb.max()}pub fn max_value(&self) -> Option<&V> {self.veb.max().and_then(|i| self.map.get(&i))}pub fn max(&self) -> Option<(usize, &V)> {self.veb.max().and_then(|i| self.map.get(&i).map(|v| (i, v)))}pub fn succ_key(&self, i: usize) -> Option<usize> {self.veb.succ(i)}pub fn succ_value(&self, i: usize) -> Option<&V> {self.veb.succ(i).and_then(|i| self.map.get(&i))}pub fn succ(&self, i: usize) -> Option<(usize, &V)> {self.veb.succ(i).and_then(|i| self.map.get(&i).map(|v| (i, v)))}pub fn pred_key(&self, i: usize) -> Option<usize> {self.veb.pred(i)}pub fn pred_value(&self, i: usize) -> Option<&V> {self.veb.pred(i).and_then(|i| self.map.get(&i))}pub fn pred(&self, i: usize) -> Option<(usize, &V)> {self.veb.pred(i).and_then(|i| self.map.get(&i).map(|v| (i, v)))}pub fn len(&self) -> usize {self.veb.len()}pub fn is_empty(&self) -> bool {self.veb.is_empty()}pub fn collect(&self) -> Vec<(usize, &V)> {self.veb.collect().into_iter().filter_map(|i| self.map.get(&i).map(|v| (i, v))).collect()}}pub enum VebSet {Internal {min: usize,max: usize,len: usize,csize: usize,summary: Box<VebSet>,chunks: HashMap<usize, VebSet>,},Leaf(u64),}impl VebSet {pub fn new(n: usize) -> Self {if n <= 64 {VebSet::Leaf(0)} else {let csize = (n as f64).sqrt().ceil() as usize;let ccount = (n + csize - 1) / csize;Self::Internal {min: 0,max: 0,csize,len: 0,summary: Box::new(VebSet::new(ccount)),chunks: HashMap::new(),}}}pub fn min(&self) -> Option<usize> {match self {Self::Internal { min, len, .. } => Some(*min).filter(|_| *len > 0),Self::Leaf(bs) => Some(bs.trailing_zeros() as usize).filter(|&i| i < 64),}}pub fn max(&self) -> Option<usize> {match self {Self::Internal { max, len, .. } => Some(*max).filter(|_| *len > 0),Self::Leaf(bs) => bs.checked_ilog2().map(|i| i as usize),}}pub fn len(&self) -> usize {match self {Self::Internal { len, .. } => *len,Self::Leaf(bs) => bs.count_ones() as usize,}}pub fn is_empty(&self) -> bool {self.len() == 0}pub fn insert(&mut self, mut i: usize) -> bool {match self {Self::Internal {min,max,csize,len,summary,chunks,} => {if *len == 0 {*min = i;*max = i;*len = 1;true} else {if i < *min {std::mem::swap(&mut i, min);}*max = (*max).max(i);if i == *min {return false;}let j = i / *csize;let k = i % *csize;let result = if let Some(chunk) = chunks.get_mut(&j) {chunk.insert(k)} else {let mut chunk = VebSet::new(*csize);assert!(chunk.insert(k));chunks.insert(j, chunk);summary.insert(j);true};if result {*len += 1;}result}}Self::Leaf(bs) => {let result = *bs >> i & 1;*bs |= 1 << i;result == 0}}}pub fn remove(&mut self, mut i: usize) -> bool {match self {Self::Internal {min,max,csize,len,summary,chunks,} => match len {0 => false,1 => {let result = i == *min;if result {*min = 0;*max = 0;*len = 0;}result}_ => {if i == *min {let j = summary.min().unwrap();i = j * *csize + chunks[&j].min().unwrap();*min = i;}let j = i / *csize;let k = i % *csize;let result = chunks.get_mut(&j).map_or(false, |chunk| chunk.remove(k));if result {*len -= 1;if chunks[&j].is_empty() {chunks.remove(&j);summary.remove(j);}if i == *max {*max = if let Some(j) = summary.max() {j * *csize + chunks[&j].max().unwrap()} else {*min};}}result}},Self::Leaf(bs) => {let result = *bs >> i & 1;*bs &= !(1 << i);result == 1}}}pub fn succ(&self, i: usize) -> Option<usize> {match self {Self::Internal {min,max,len,csize,summary,chunks,..} => {let j = i / csize;let k = i % csize;match () {() if *len == 0 || *max <= i => None,() if i < *min => Some(*min),() => multi_or_else!(chunks.get(&j).and_then(|chunk| chunk.succ(k)).map(|k1| j * csize + k1),summary.succ(j).map(|j1| j1 * csize + chunks[&j1].min().unwrap())),}}&Self::Leaf(bs) => match i {63 => None,_ => Some(i + 1 + (bs >> (i + 1)).trailing_zeros() as usize).filter(|&i1| i1 < 64),},}}pub fn pred(&self, i: usize) -> Option<usize> {match self {Self::Internal {min,max,csize,len,summary,chunks,} => {let j = i / csize;let k = i % csize;match () {() if *len == 0 || i <= *min => None,() if *max < i => Some(*max),() => multi_or_else!(chunks.get(&j).and_then(|chunk| chunk.pred(k)).map(|k1| { j * csize + k1 }),summary.pred(j).map(|j1| { j1 * csize + chunks[&j1].max().unwrap() }),Some(*min)),}}&Self::Leaf(bs) => (bs & ((1 << i) - 1)).checked_ilog2().map(|j| j as usize),}}pub fn contains(&self, i: usize) -> bool {match self {#[allow(unused_variables)]Self::Internal {min,max,csize,len,summary,chunks,} => {let j = i / csize;let k = i % csize;*len != 0&& (i == *min || chunks.get(&j).map_or(false, |chunk| chunk.contains(k)))}Self::Leaf(bs) => bs >> i & 1 == 1,}}pub fn collect(&self) -> Vec<usize> {let mut result = Vec::with_capacity(self.len());let mut i = self.min();for _ in 0..self.len() {result.push(i.unwrap());i = self.succ(i.unwrap());}result}}impl std::fmt::Debug for VebSet {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {f.debug_set().entries(self.collect()).finish()}}}// }}}