結果

問題 No.2248 max(C)-min(C)
ユーザー akakimidoriakakimidori
提出日時 2023-04-09 20:13:10
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 1 ms
6,820 KB
testcase_10 AC 1 ms
6,820 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 1 ms
6,820 KB
testcase_16 AC 1 ms
6,816 KB
testcase_17 AC 1 ms
6,820 KB
testcase_18 AC 60 ms
25,912 KB
testcase_19 AC 8 ms
6,820 KB
testcase_20 AC 68 ms
25,948 KB
testcase_21 AC 62 ms
24,704 KB
testcase_22 AC 43 ms
17,408 KB
testcase_23 AC 29 ms
12,160 KB
testcase_24 AC 11 ms
6,816 KB
testcase_25 AC 61 ms
22,912 KB
testcase_26 AC 55 ms
21,284 KB
testcase_27 AC 60 ms
24,728 KB
testcase_28 AC 7 ms
6,820 KB
testcase_29 AC 58 ms
21,504 KB
testcase_30 AC 23 ms
9,984 KB
testcase_31 AC 66 ms
25,600 KB
testcase_32 AC 13 ms
6,820 KB
testcase_33 AC 21 ms
8,960 KB
testcase_34 AC 65 ms
25,600 KB
testcase_35 AC 68 ms
25,680 KB
testcase_36 AC 65 ms
25,600 KB
testcase_37 AC 35 ms
14,208 KB
testcase_38 AC 63 ms
24,924 KB
testcase_39 AC 64 ms
26,780 KB
testcase_40 AC 63 ms
24,960 KB
testcase_41 AC 54 ms
21,760 KB
testcase_42 AC 61 ms
25,116 KB
testcase_43 AC 56 ms
22,272 KB
testcase_44 AC 64 ms
25,400 KB
testcase_45 AC 49 ms
19,968 KB
testcase_46 AC 26 ms
11,180 KB
testcase_47 AC 62 ms
24,960 KB
testcase_48 AC 164 ms
24,832 KB
testcase_49 AC 286 ms
25,472 KB
testcase_50 AC 289 ms
25,600 KB
testcase_51 AC 300 ms
25,728 KB
testcase_52 AC 290 ms
25,600 KB
testcase_53 AC 36 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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/198520186
pub 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>
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<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 ----------
0