結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー rhoo
提出日時 2025-10-30 12:54:41
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 2,461 bytes
コンパイル時間 12,298 ms
コンパイル使用メモリ 399,380 KB
実行使用メモリ 22,776 KB
最終ジャッジ日時 2025-11-17 20:41:25
合計ジャッジ時間 13,851 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]



fn main(){
    proconio::input!{
        n:usize,
        mut a:[usize;n],
    }

    use std::iter::*;
    let mut prev=once(!0).chain(0..n-1).collect::<Vec<_>>();
    let mut next=(1..n).chain(once(!0)).collect::<Vec<_>>();
    let mut que=(0..n).filter(|&i|a[i]==0).collect::<Vec<_>>();
    
    let mut perm=vec![!0;n];
    let mut it=0;
    
    while let Some(i)=que.pop(){
        perm[i]=it;
        it+=1;
        for ni in [prev[i],next[i]]{
            if ni==!0{
                continue;
            }
            if a[ni]==0{
                println!("0");
                return;
            }
            a[ni]-=1;
            if a[ni]==0{
                que.push(ni);
            }
        }

        if next[i]!=!0{
            prev[next[i]]=prev[i];
        }
        if prev[i]!=!0{
            next[prev[i]]=next[i];
        }
    }

    if it!=n{
        println!("0");
        return;
    }
    
    let (root,tree)=cartesian_tree(&perm);

    const MOD:u64=998244353;
    fn rec(tree:&[Node],v:usize)->(u64,u64){
        if v==!0{
            return (0,1);
        }
        let (lsize,lprod)=rec(tree,tree[v].left);
        let (rsize,rprod)=rec(tree,tree[v].right);
        let size=lsize+rsize+1;
        (size,lprod*rprod%MOD*size%MOD)
    }

    let mut inv=1;
    let mut k=MOD-2;
    let (_,mut pow2)=rec(&tree,root);
    while k>0{
        if k&1==1{
            inv=inv*pow2%MOD;
        }
        pow2=pow2*pow2%MOD;
        k>>=1;
    }

    let mut ans=inv;
    for i in 1..=n{
        ans=ans*i as u64%MOD;
    }

    println!("{ans}");
}



#[derive(Clone,Copy)]
struct Node{
    par:usize,
    left:usize,
    right:usize,
}


// 最大の値が根
// 値が同じ場合はindexが小さいほうが親になる
// (root,グラフ) を返す
fn cartesian_tree<T:Ord>(a:&[T])->(usize,Vec<Node>){
    assert!(!a.is_empty());
    
    let mut tree=vec![Node{par:!0,left:!0,right:!0};a.len()];
    let mut stack=vec![0];
    
    let get_last=|a:&[usize]|*a.last().unwrap();

    for i in 1..a.len(){
        let mut last=!0;
        while 0<stack.len() && a[get_last(&stack)]<a[i]{
            last=stack.pop().unwrap();
        }

        if let Some(&par)=stack.last(){
            tree[i].par=par;
            tree[par].right=i;
        }
        if last!=!0{
            tree[last].par=i;
            tree[i].left=last;
        }
        
        stack.push(i);
    }

    (stack[0],tree)
}
0