結果

問題 No.2988 Min-Plus Convolution Query
コンテスト
ユーザー akakimidori
提出日時 2024-12-13 21:48:10
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 766 ms / 2,000 ms
コード長 6,399 bytes
コンパイル時間 15,200 ms
コンパイル使用メモリ 402,392 KB
実行使用メモリ 65,384 KB
最終ジャッジ日時 2024-12-13 21:48:46
合計ジャッジ時間 32,612 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Write;

fn run() {
    input! {
        n: usize,
        q: usize,
        a: [i32; n],
        b: [i32; n],
        ask: [(usize1, i32, usize); q],
    }
    let ask = ask
        .into_iter()
        .map(|p| (p.0, p.1, p.2 - 2))
        .collect::<Vec<_>>();
    let mut memo = a.iter().map(|a| (*a, 0)).collect::<Vec<_>>();
    let mut list = vec![];
    for (i, &(x, v, _)) in ask.iter().enumerate() {
        let po = &mut memo[x];
        if i > 0 {
            list.push((x, po.1, i, po.0));
        }
        *po = (v, i);
    }
    for (i, (v, l)) in memo.into_iter().enumerate() {
        list.push((i, l, q, v));
    }
    list.sort_by_key(|p| p.0);
    let inf = 10i32.pow(9) * 2 + 1;
    let mut dp = ask.iter().map(|p| (p.2, inf)).collect::<Vec<_>>();
    dp.sort();
    dp.dedup();
    let mut ans = vec![inf; q];
    let mut dfs = vec![(0, q, list, dp)];
    let mut elem = vec![0; 2 * n];
    let mut id = 0;
    while let Some((l, r, list, mut dp)) = dfs.pop() {
        let mut left = vec![];
        let mut right = vec![];
        let mut mid = vec![];
        let m = (l + r) / 2;
        for (x, s, t, v) in list {
            if s <= l && r <= t {
                mid.push((x, v));
                continue;
            }
            if s < m {
                left.push((x, s, t, v));
            }
            if m < t {
                right.push((x, s, t, v));
            }
        }
        if mid.len() > 0 {
            let pos = smawk(dp.len(), mid.len(), &|row, i, j| {
                let x = dp[row].0;
                let y = mid[i].0;
                let z = mid[j].0;
                if x < z {
                    false
                } else if x >= y + n {
                    true
                } else {
                    mid[i].1 + b[x - y] > mid[j].1 + b[x - z]
                }
            });
            for (dp, &i) in dp.iter_mut().zip(pos.iter()) {
                let (i, v) = mid[i];
                let x = dp.0;
                if i <= x && x - i < n {
                    dp.1.chmin(v + b[x - i]);
                }
            }
        }
        if l + 1 == r {
            ans[l] = dp[0].1;
            continue;
        }
        let ask = &ask[l..r];
        let (p, q) = ask.split_at(m - l);
        id += 1;
        for p in p.iter() {
            elem[p.2] = id;
        }
        let mut ndp = dp.clone();
        ndp.retain(|p| elem[p.0] == id);
        dfs.push((l, m, left, ndp));
        id += 1;
        for p in q.iter() {
            elem[p.2] = id;
        }
        dp.retain(|p| elem[p.0] == id);
        dfs.push((m, r, right, dp));
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for a in ans {
        writeln!(out, "{}", a).ok();
    }
}

fn main() {
    run();
}

fn smawk<F>(row: usize, col: usize, select: &F) -> Vec<usize>
where
    F: Fn(usize, usize, usize) -> bool,
{
    let mut buf = vec![0; col + 2 * row];
    let (col, mut buf) = buf.split_at_mut(col);
    for (i, c) in col.iter_mut().enumerate() {
        *c = i;
    }
    let mut stack: Vec<(usize, &[usize])> = vec![(row, col)];
    loop {
        let &(h, col) = stack.last().unwrap();
        if h == 1 {
            break;
        }
        let step = 1 << (stack.len() - 1);
        let mut po = 0;
        for &c in col.iter() {
            while po > 0 && select(step * (po - 1) + step - 1, buf[po - 1], c) {
                po -= 1;
            }
            if po < h {
                buf[po] = c;
                po += 1;
            }
        }
        let (ncol, tail) = buf.split_at_mut(po);
        buf = tail;
        stack.last_mut().unwrap().1 = ncol;
        stack.push((h / 2, ncol));
    }
    let mut ans = vec![0; row];
    while let Some((h, col)) = stack.pop() {
        for i in (0..(h / 2)).rev() {
            ans[2 * i + 1] = ans[i];
        }
        let step = 1 << stack.len();
        let mut j = 0;
        for (i, ans) in ans[..h].chunks_mut(2).enumerate() {
            let end = if ans.len() == 1 {
                *col.last().unwrap()
            } else {
                ans[1]
            };
            let row = 2 * i * step + step - 1;
            let mut pos = col[j];
            while col[j] != end {
                j += 1;
                if select(row, pos, col[j]) {
                    pos = col[j];
                }
            }
            ans[0] = pos;
        }
    }
    ans
}

// ---------- 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 chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------
0