結果
| 問題 |
No.3371 Add Insert Operations
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2025-10-29 16:50:53 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 173 ms / 2,000 ms |
| コード長 | 12,214 bytes |
| コンパイル時間 | 14,759 ms |
| コンパイル使用メモリ | 397,552 KB |
| 実行使用メモリ | 32,144 KB |
| 最終ジャッジ日時 | 2025-11-17 20:36:19 |
| 合計ジャッジ時間 | 18,065 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
コンパイルメッセージ
warning: associated items `new`, `set`, `get`, `max_right`, and `min_left` are never used
--> src/main.rs:118:8
|
117 | impl<M:Monoid> Segtree<M>{
| ------------------------- associated items in this implementation
118 | fn new(n:usize)->Self{
| ^^^
...
126 | fn set(&mut self,mut i:usize,v:M::S){
| ^^^
...
137 | fn get(&self,i:usize)->M::S{
| ^^^
...
182 | fn max_right(&self,mut l:usize,mut f:impl FnMut(M::S)->bool)->usize{
| ^^^^^^^^^
...
214 | fn min_left(&self,mut r:usize,mut f:impl FnMut(M::S)->bool)->usize{
| ^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: type alias `ModInt1000000007` is never used
--> src/main.rs:273:6
|
273 | type ModInt1000000007=ModInt<1000000007>;
| ^^^^^^^^^^^^^^^^
warning: methods `val` and `pow` are never used
--> src/main.rs:456:8
|
450 | trait ModIntBase:Default+std::str::FromStr+Copy+Eq+std::hash::Hash+std::fmt::Display+std::fmt::Debug
| ---------- methods in this trait
...
456 | fn val(self)->u32;
| ^^^
...
459 | fn pow(self,k:u64)->Self;
| ^^^
warning: methods `inv`, `perm`, and `multi_choose` are never used
--> src/main.rs:498:8
|
472 | impl<M:ModIntBase> Pre<M>{
| ------------------------- methods in this implementation
...
498 | fn inv(&self,n:usize)->M{
| ^^^
...
503 | fn perm(&self,n:usize,k:usize)->M{
| ^^^^
...
517 | fn multi_choose(&self,n:usize,k:usize)->M{
| ^^^^^^^^^^^^
ソースコード
#![allow(non_snake_case)]
fn main(){
proconio::input!{
n:usize,
a:[usize;n],
}
// naive(n,&a);
use std::collections::*;
let mut set=(0..n).map(|i|(i,a[i])).collect::<BTreeSet<_>>();
let mut perm=vec![!0;n];
let mut que=(0..n).filter(|&i|a[i]==0).collect::<Vec<_>>();
let mut it=0..;
while let Some(i)=que.pop(){
let &(ci,val)=set.range((i,0)..).next().unwrap();
assert!(i==ci);
perm[i]=it.next().unwrap();
set.remove(&(i,val));
macro_rules! update{
($ni:expr,$val:expr)=>{
set.remove(&($ni,$val));
if $val==0{
println!("0");
return;
}
set.insert(($ni,$val-1));
if $val==1{
que.push($ni);
}
}
}
if let Some(&(ni,val))=set.range((i,0)..).next(){
update!(ni,val);
}
if let Some(&(ni,val))=set.range(..(i,0)).rev().next(){
update!(ni,val);
}
}
if !set.is_empty(){
println!("0");
return;
}
impl_monoid!(Max,(usize,usize),(0,0),|a:(usize,usize),b:(usize,usize)|a.max(b));
let seg=Segtree::<Max>::from((0..n).map(|i|(perm[i],i)).collect::<Vec<_>>());
type M=ModInt998244353;
let pre=Pre::<M>::new(n);
fn rec(seg:&Segtree<Max>,l:usize,r:usize,pre:&Pre<M>)->M{
if l==r{
M::new(1)
} else{
let (_,mi)=seg.prod(l..r);
pre.choose(r-l-1,mi-l)*rec(seg,l,mi,pre)*rec(seg,mi+1,r,pre)
}
}
let ans=rec(&seg,0,n,&pre);
println!("{ans}");
}
// fn naive(n:usize,a:&[usize]){
// use itertools::*;
// let mut ans=0;
// for is in (0..n).permutations(n){
// let mut b=vec![!0;n];
// for &i in &is{
// b[i]=0;
// if let Some(ni)=(0..i).rev().find(|&ni|b[ni]!=!0){
// b[ni]+=1;
// }
// if let Some(ni)=(i+1..n).find(|&ni|b[ni]!=!0){
// b[ni]+=1;
// }
// }
// if a==b{
// ans+=(a==&b) as usize;
// }
// }
// eprintln!("#{ans}");
// }
#[derive(Clone)]
struct Segtree<M:Monoid>{
n:usize,
size:usize,
a:Vec<M::S>,
}
impl<M:Monoid> From<Vec<M::S>> for Segtree<M>{
fn from(v:Vec<M::S>)->Self{
let n=v.len();
let size=n.next_power_of_two();
let mut a=vec![M::e();size*2];
a[size..size+n].copy_from_slice(&v);
for i in (1..size).rev(){
a[i]=M::op(a[i*2],a[i*2+1]);
}
Segtree{n,size,a}
}
}
impl<M:Monoid> Segtree<M>{
fn new(n:usize)->Self{
let size=n.next_power_of_two();
Segtree{
n,size,
a:vec![M::e();size*2],
}
}
fn set(&mut self,mut i:usize,v:M::S){
assert!(i<self.n);
i+=self.size;
self.a[i]=v;
i/=2;
while i!=0{
self.a[i]=M::op(self.a[i*2],self.a[i*2+1]);
i/=2;
}
}
fn get(&self,i:usize)->M::S{
assert!(i<self.n);
self.a[i+self.size]
}
fn prod(&self,range:impl std::ops::RangeBounds<usize>)->M::S{
use std::ops::Bound::*;
let mut u=match range.start_bound(){
Included(&a)=>a,
Excluded(&a)=>a+1,
Unbounded=>0,
};
let mut v=match range.end_bound(){
Included(&a)=>a+1,
Excluded(&a)=>a,
Unbounded=>self.n,
};
assert!(u<=v && v<=self.n);
if (u,v)==(0,self.n){
return self.a[1];
}
let mut um=M::e();
let mut vm=M::e();
u+=self.size;
v+=self.size;
while u<v{
if u&1!=0{
um=M::op(um,self.a[u]);
u+=1;
}
if v&1!=0{
v-=1;
vm=M::op(self.a[v],vm);
}
u/=2;
v/=2;
}
M::op(um,vm)
}
// l..rがtrueで、l..=rがfalse
fn max_right(&self,mut l:usize,mut f:impl FnMut(M::S)->bool)->usize{
assert!(l<=self.n && f(M::e()));
if l==self.n{
return self.n;
}
l+=self.size;
let mut m=M::e();
loop{
l>>=l.trailing_zeros();
if !f(M::op(m,self.a[l])){
while l<self.size{
l*=2;
let res=M::op(m,self.a[l]);
if f(res){
m=res;
l+=1;
}
}
return l-self.size;
}
m=M::op(m,self.a[l]);
l+=1;
if l&l.wrapping_neg()==l{
return self.n;
}
}
}
// l..rがtrueで、l-1..rがfalse
fn min_left(&self,mut r:usize,mut f:impl FnMut(M::S)->bool)->usize{
assert!(r<=self.n && f(M::e()));
if r==0{
return 0;
}
r+=self.size;
let mut m=M::e();
loop{
r-=1;
r>>=r.trailing_ones();
r=r.max(1);
if !f(M::op(self.a[r],m)){
while r<self.size{
r=r*2+1;
let res=M::op(self.a[r],m);
if f(res){
m=res;
r-=1;
}
}
return r+1-self.size;
}
m=M::op(self.a[r],m);
if r&r.wrapping_neg()==r{
return 0;
}
}
}
}
trait Monoid{
type S:Copy;
fn e()->Self::S;
fn op(left:Self::S,right:Self::S)->Self::S;
}
#[macro_export]
macro_rules! impl_monoid{
($t:ident,$item:ty,$e:expr,$op:expr)=>{
#[derive(Clone,Copy)]
struct $t();
impl Monoid for $t{
type S=$item;
fn e()->$item{ $e }
fn op(left:$item,right:$item)->$item{
$op(left,right)
}
}
};
}
type ModInt998244353=ModInt<998244353>;
type ModInt1000000007=ModInt<1000000007>;
#[derive(Clone,Copy,PartialEq,Eq,Default,Hash)]
struct ModInt<const MOD:u32>(u32);
impl<const MOD:u32> ModIntBase for ModInt<MOD>{
fn modulus()->u32{ MOD }
fn val(self)->u32{ self.0 }
fn new(v:impl RemU32)->Self{ Self(v.rem_u32(MOD)) }
fn inv(self)->Self{
assert!(self.0!=0);
let (mut a,mut b)=(self.0 as i64,MOD as i64);
let (mut u,mut v)=(1,0);
while b!=0{
let t=a/b;
(a,b)=(b,a-t*b);
(u,v)=(v,u-t*v);
}
assert!(a==1);
if u<0{
u+=MOD as i64;
}
Self(u as u32)
}
fn pow(self,mut k:u64)->Self{
let mut pow2=self;
let mut ret=Self(1);
while k>0{
if k&1==1{
ret*=pow2;
}
pow2*=pow2;
k>>=1;
}
ret
}
}
impl<const MOD:u32> std::fmt::Display for ModInt<MOD>{
fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{
write!(f,"{}",self.0)
}
}
impl<const MOD:u32> std::fmt::Debug for ModInt<MOD>{
fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{
write!(f,"{}",self.0)
}
}
impl<const MOD:u32> std::ops::Add for ModInt<MOD>{
type Output=Self;
fn add(self,a:Self)->Self{
let mut new=self.0+a.0;
if MOD<=new{
new-=MOD;
}
Self(new)
}
}
impl<const MOD:u32> std::ops::Sub for ModInt<MOD>{
type Output=Self;
fn sub(self,a:Self)->Self{
let mut new=self.0-a.0;
if 0>new as i32{
new+=MOD;
}
Self(new)
}
}
impl<const MOD:u32> std::ops::Mul for ModInt<MOD>{
type Output=Self;
fn mul(self,a:Self)->Self{
Self((self.0 as u64*a.0 as u64%MOD as u64) as u32)
}
}
impl<const MOD:u32> std::ops::Div for ModInt<MOD>{
type Output=Self;
fn div(self,a:Self)->Self{
self*a.inv()
}
}
impl<const MOD:u32> std::ops::Neg for ModInt<MOD>{
type Output=Self;
fn neg(self)->Self{
if self.0==0{
return self;
}
Self(MOD-self.0)
}
}
impl<const MOD:u32> std::str::FromStr for ModInt<MOD>{
type Err=<u64 as std::str::FromStr>::Err;
fn from_str(s:&str)->Result<Self,Self::Err>{
let x=s.parse::<u64>()?;
Ok(Self::new(x))
}
}
macro_rules! impl_modint_ops{
($trait:ident,$func:ident,$assign_trait:ident,$assign_func:ident,$op:tt)=>{
impl<const MOD:u32> std::ops::$assign_trait for ModInt<MOD>{
fn $assign_func(&mut self,a:Self){
*self=*self $op a
}
}
impl<T:RemU32,const MOD:u32> std::ops::$trait<T> for ModInt<MOD>{
type Output=Self;
fn $func(self,a:T)->Self{
self $op Self::new(a)
}
}
impl<T:RemU32,const MOD:u32> std::ops::$assign_trait<T> for ModInt<MOD>{
fn $assign_func(&mut self,a:T){
*self=*self $op Self::new(a)
}
}
}
}
impl_modint_ops!(Add,add,AddAssign,add_assign,+);
impl_modint_ops!(Sub,sub,SubAssign,sub_assign,-);
impl_modint_ops!(Mul,mul,MulAssign,mul_assign,*);
impl_modint_ops!(Div,div,DivAssign,div_assign,/);
impl<const MOD:u32> std::iter::Sum for ModInt<MOD>{
fn sum<I:Iterator<Item=Self>>(iter:I)->Self{
iter.fold(Self(0),|sum,x|sum+x)
}
}
impl<const MOD:u32> std::iter::Product for ModInt<MOD>{
fn product<I:Iterator<Item=Self>>(iter:I)->Self{
iter.fold(Self(1),|prod,x|prod*x)
}
}
trait RemU32{
fn rem_u32(self,m:u32)->u32;
}
macro_rules! impl_rem_u32{
($($ty:tt),*)=>{
$(
impl RemU32 for $ty{
fn rem_u32(self,m:u32)->u32{
(self as i64).rem_euclid(m as i64) as _
}
}
)*
}
}
impl_rem_u32!(i32,i64);
macro_rules! impl_rem_u32{
($($ty:tt),*)=>{
$(
impl RemU32 for $ty{
fn rem_u32(self,m:u32)->u32{
(self%(m as $ty)) as _
}
}
)*
}
}
impl_rem_u32!(u32,u64,usize);
trait ModIntBase:Default+std::str::FromStr+Copy+Eq+std::hash::Hash+std::fmt::Display+std::fmt::Debug
+std::ops::Neg<Output=Self>+std::ops::Add<Output=Self>+std::ops::Sub<Output=Self>
+std::ops::Mul<Output=Self>+std::ops::Div<Output=Self>
+std::ops::AddAssign+std::ops::SubAssign+std::ops::MulAssign+std::ops::DivAssign
{
fn modulus()->u32;
fn val(self)->u32;
fn new(v:impl RemU32)->Self;
fn inv(self)->Self;
fn pow(self,k:u64)->Self;
}
// Modを超える数はpanicする
// 注意：
// Modは素数
// multi_choose(n,k)を使うときは，fac(n+k-1)まで必要になる
struct Pre<M:ModIntBase>{
fac:Vec<M>,
finv:Vec<M>,
}
impl<M:ModIntBase> Pre<M>{
fn new(n:usize)->Self{
assert!(n<M::modulus() as usize);
let mut fac=vec![M::new(1);n+1];
for i in 1..=n{
fac[i]=fac[i-1]*M::new(i);
}
let mut finv=vec![M::new(0);n+1];
finv[n]=fac[n].inv();
for i in (1..=n).rev(){
finv[i-1]=finv[i]*M::new(i);
}
Self{fac,finv}
}
fn fac(&self,n:usize)->M{
self.fac[n]
}
fn finv(&self,n:usize)->M{
self.finv[n]
}
fn inv(&self,n:usize)->M{
assert!(n!=0);
self.finv[n]*self.fac[n-1]
}
fn perm(&self,n:usize,k:usize)->M{
if n<k || (n as i64)<0 || (k as i64)<0{
return M::new(0);
}
self.fac(n)*self.finv(n-k)
}
fn choose(&self,n:usize,k:usize)->M{
if n<k || (n as i64)<0 || (k as i64)<0{
return M::new(0);
}
self.fac(n)*self.finv(k)*self.finv(n-k)
}
fn multi_choose(&self,n:usize,k:usize)->M{
if (n as i64)<0 || (k as i64)<0{
return M::new(0);
}
if n==0 && k==0{
return M::new(1);
}
self.choose(n+k-1,k)
}
}