結果

問題 No.2735 Demarcation
コンテスト
ユーザー CoCo_Japan_pan
提出日時 2024-04-20 15:01:10
言語 Rust
(1.83.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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 {}
    }
}
0