fn main() { input! { n: usize, a: [u32; n], b: [u32; n], } let mut solver = PriorityUndoDS::new(Solver(vec![])); let mut p = vec![]; for (i, (a, b)) in a.iter().zip(b.iter()).enumerate() { let mut v = vec![*a, *b, (*a + *b) / 2]; v.sort(); let u = v.pop().unwrap(); solver.update((u, i), u); p.push(v); } let mut ans = *solver.peek().unwrap() - *solver.0.last().unwrap(); while let Some(((_, k), _)) = solver.undo() { if let Some(v) = p[k].pop() { solver.update((v, k), v); ans = ans.min(*solver.peek().unwrap() - *solver.0.last().unwrap()); } else { break; } } println!("{}", ans); } struct Solver(Vec); impl UndoDS for Solver { type Arg = (u32, usize); fn update(&mut self, arg: Self::Arg) { let v = arg.0.min(self.0.last().cloned().unwrap_or(std::u32::MAX)); self.0.push(v); } fn undo(&mut self) { self.0.pop(); } } // ---------- 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::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // ---------- begin priorityqueue-like undoing ds ---------- // 参考文献: https://codeforces.com/blog/entry/111117 // 記事中ではsetで丁寧に管理してlogを落としてる // この実装ではコメントにあるソートでlogつける実装にしてる // 優先度が大きいものから消す // 操作回数の合計をN // データ構造の1回の操作の計算量をT // O(N(logN)^2 + NTlogN) // のはず // verify: https://codeforces.com/contest/603/submission/198520186 pub trait UndoDS { type Arg: Clone; fn update(&mut self, arg: Self::Arg); fn undo(&mut self); } pub struct PriorityUndoDS { data: DS, memo: Vec<(DS::Arg, T, T)>, } impl PriorityUndoDS where DS: UndoDS, T: Ord + Copy, { pub fn new(data: DS) -> Self { Self { data: data, memo: vec![], } } pub fn update(&mut self, arg: DS::Arg, v: T) { self.data.update(arg.clone()); let s = self.memo.last().map_or(v, |p| p.2.max(v)); self.memo.push((arg, v, s)); } pub fn undo(&mut self) -> Option<(DS::Arg, T)> { if self.memo.is_empty() { return None; } let k = self.memo.iter().rev().position(|p| p.1 == p.2).unwrap() + 1; let s = self.memo.len().saturating_sub(2 * k - 1); for _ in s..self.memo.len() { self.data.undo(); } self.memo[s..].sort_by_key(|p| p.1); let res = self.memo.pop().unwrap(); if s < self.memo.len() { let mut pre = self .memo .get(s - 1) .map(|p| p.2) .or(self.memo.get(s).map(|p| p.1)) .unwrap(); for memo in self.memo[s..].iter_mut() { pre = pre.max(memo.1); memo.2 = pre; self.data.update(memo.0.clone()); } } Some((res.0, res.1)) } pub fn peek(&self) -> Option<&T> { self.memo.last().map(|p| &p.2) } pub fn all_undo(&mut self) { for _ in 0..self.memo.len() { self.undo(); } } } impl std::ops::Deref for PriorityUndoDS { type Target = DS; fn deref(&self) -> &Self::Target { &self.data } } impl std::ops::DerefMut for PriorityUndoDS { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.data } } // ---------- end priorityqueue-like undoing ds ----------