結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 2023-04-09 20:13:10 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 300 ms / 3,000 ms |
コード長 | 5,023 bytes |
コンパイル時間 | 15,579 ms |
コンパイル使用メモリ | 400,720 KB |
実行使用メモリ | 26,780 KB |
最終ジャッジ日時 | 2024-10-05 00:09:20 |
合計ジャッジ時間 | 20,623 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
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<u32>);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::<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 ----------// ---------- 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/198520186pub trait UndoDS {type Arg: Clone;fn update(&mut self, arg: Self::Arg);fn undo(&mut self);}pub struct PriorityUndoDS<DS: UndoDS, T> {data: DS,memo: Vec<(DS::Arg, T, T)>,}impl<DS, T> PriorityUndoDS<DS, T>whereDS: 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<DS: UndoDS, T> std::ops::Deref for PriorityUndoDS<DS, T> {type Target = DS;fn deref(&self) -> &Self::Target {&self.data}}impl<DS: UndoDS, T> std::ops::DerefMut for PriorityUndoDS<DS, T> {fn deref_mut(&mut self) -> &mut Self::Target {&mut self.data}}// ---------- end priorityqueue-like undoing ds ----------