#975432 (Rust) No.2735 Demarcation

提出ソース

結果

問題	No.2735 Demarcation
ユーザー	CoCo_Japan_pan
提出日時	2024-04-20 15:01:10
言語	Rust (1.77.0 + proconio)
結果	WA
実行時間	-
コード長	8,194 bytes
コンパイル時間	13,801 ms
コンパイル使用メモリ	379,704 KB
実行使用メモリ	19,396 KB
最終ジャッジ日時	2024-10-12 10:41:34
合計ジャッジ時間	17,681 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
pub use __cargo_equip::prelude::*;

use proconio::marker::{Bytes, Chars, Isize1, Usize1};
use proconio::{input, input_interactive};
#[allow(unused_imports)]
use proconio_derive::fastout;

/*#[fastout]
fn main() {
    input! {
        N: usize,
        X: [usize; N],
        Q: usize,
    }
    let mut cnt_memo = vec![0; N + 1];
    for _ in 0..Q {
        input! {
            l: Usize1,
            r: Usize1,
            S: u64,
        }
        // 半開区間[l, r)とする
        let r = r + 1;
        // 最大値なし
        if 2_u64.pow((r - l - 1) as u32) <= S {
            println!("-1");
            continue;
        }
        // kについて二分探索
        let mut left_k = 0;
        let mut right_k = r - l;
        while right_k - left_k > 1 {
            let mid_k = (right_k + left_k) / 2;
            // 事前に尺取り法で、各rについて、[l, r)の種類数がk以下となる最小のlを求めておく
            let min_left = {
                let mut ret = vec![0; r - l + 1];
                let mut left = r;
                let mut kind = 0;
                for right in (l+1..=r).rev() {
                    while left > l {
                        if kind < mid_k {
                            left -= 1;
                            if cnt_memo[X[left]] == 0 {
                                kind += 1;
                            }
                            cnt_memo[X[left]] += 1;
                        } else if kind == mid_k && cnt_memo[X[left - 1]] > 0 {
                            left -= 1;
                            cnt_memo[X[left]] += 1;
                        } else {
                            cnt_memo[X[right - 1]] -= 1;
                            if cnt_memo[X[right - 1]] == 0 {
                                kind -= 1;
                            }
                            break;
                        }
                    }
                    ret[right - l] = left;
                }
                // 最後にcnt_memoをもとに戻す
                for i in l..r {
                    cnt_memo[X[i]] = 0;
                }
                ret
            };
            // A[l..r]までの通り数
            let mut dp = vec![0; r - l + 1];
            let mut dp_cum = vec![0; r - l + 2];
            dp[0] = 1;
            dp_cum[1] = 1;
            for right in l+1..=r {
                // min_left[right - l]..rightまでの通り数を足す
                let cur_min_left = min_left[right - l];
                dp[right - l] = dp_cum[right - l] - dp_cum[cur_min_left - l];
                dp_cum[right - l + 1] = dp_cum[right - l] + dp[right - l];
            }
            debug!(l, r, mid_k, dp[r - l]);
            debug!(dp, dp_cum);
            if dp[r - l] <= S {
                left_k = mid_k;
            } else {
                right_k = mid_k;
            }
        }
        println!("{}", left_k);
    }
}*/
fn main() {
    let __proconio_stdout = ::std::io::stdout();
    let mut __proconio_stdout = ::std::io::BufWriter::new(__proconio_stdout.lock());
    #[allow(unused_macros)]
    macro_rules ! print { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: write ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    #[allow(unused_macros)]
    macro_rules ! println { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: writeln ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    let __proconio_res = {
        input! { N : usize , X : [usize ; N] , Q : usize , }
        let mut cnt_memo = vec![0; N + 1];
        for _ in 0..Q {
            input! { l : Usize1 , r : Usize1 , S : u64 , }
            let r = r + 1;
            if 2_u64.pow((r - l - 1) as u32) <= S {
                println!("-1");
                continue;
            }
            let mut left_k = 0;
            let mut right_k = r - l;
            while right_k - left_k > 1 {
                let mid_k = (right_k + left_k) / 2;
                let min_left = {
                    let mut ret = vec![0; r - l + 1];
                    let mut left = r;
                    let mut kind = 0;
                    for right in (l + 1..=r).rev() {
                        while left > l {
                            if kind < mid_k {
                                left -= 1;
                                if cnt_memo[X[left]] == 0 {
                                    kind += 1;
                                }
                                cnt_memo[X[left]] += 1;
                            } else if kind == mid_k && cnt_memo[X[left - 1]] > 0 {
                                left -= 1;
                                cnt_memo[X[left]] += 1;
                            } else {
                                cnt_memo[X[right - 1]] -= 1;
                                if cnt_memo[X[right - 1]] == 0 {
                                    kind -= 1;
                                }
                                break;
                            }
                        }
                        ret[right - l] = left;
                    }
                    for i in l..r {
                        cnt_memo[X[i]] = 0;
                    }
                    ret
                };
                let mut dp = vec![0; r - l + 1];
                let mut dp_cum = vec![0; r - l + 2];
                dp[0] = 1;
                dp_cum[1] = 1;
                for right in l + 1..=r {
                    let cur_min_left = min_left[right - l];
                    dp[right - l] = dp_cum[right - l] - dp_cum[cur_min_left - l];
                    dp_cum[right - l + 1] = dp_cum[right - l] + dp[right - l];
                }
                debug!(l, r, mid_k, dp[r - l]);
                debug!(dp, dp_cum);
                if dp[r - l] <= S {
                    left_k = mid_k;
                } else {
                    right_k = mid_k;
                }
            }
            println!("{}", left_k);
        }
    };
    <::std::io::BufWriter<::std::io::StdoutLock> as ::std::io::Write>::flush(
        &mut __proconio_stdout,
    )
    .unwrap();
    return __proconio_res;
}

#[macro_export]
macro_rules! mat {
    ($($e:expr),*) => { vec![$($e),*] };
    ($($e:expr,)*) => { vec![$($e),*] };
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {
        if $a > $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {
        if $a < $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

// The following code was expanded by `cargo-equip`.

///  # Procedural macros
/// 
///  - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod proconio_derive {pub use crate::__cargo_equip::macros::proconio_derive::*;#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_derive_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_derive_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
    }

    pub(crate) mod macros {
        pub mod proconio_derive {pub use crate::{__cargo_equip_macro_def_proconio_derive_derive_readable as derive_readable,__cargo_equip_macro_def_proconio_derive_fastout as fastout};}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod proconio_derive {}
    }
}

yukicoder

結果

テストケース

ソースコード