結果
問題 | No.2616 中央番目の中央値 |
ユーザー |
![]() |
提出日時 | 2024-01-26 21:40:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 573 ms / 2,000 ms |
コード長 | 3,500 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 137,568 KB |
最終ジャッジ日時 | 2024-09-28 07:54:03 |
合計ジャッジ時間 | 11,459 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
from sys import stdininput=lambda :stdin.readline()[:-1]class segtree():def __init__(self,init,func,ide):self.n=len(init)self.func=funcself.ide=ideself.size=1<<(self.n-1).bit_length()self.tree=[self.ide for i in range(2*self.size)]for i in range(self.n):self.tree[self.size+i]=init[i]for i in range(self.size-1,0,-1):self.tree[i]=self.func(self.tree[2*i], self.tree[2*i|1])def update(self,k,x):k+=self.sizeself.tree[k]=xk>>=1while k:self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1])k>>=1def get(self,i):return self.tree[i+self.size]def query(self,l,r):l+=self.sizer+=self.sizel_res=self.ider_res=self.idewhile l<r:if l&1:l_res=self.func(l_res,self.tree[l])l+=1if r&1:r-=1r_res=self.func(self.tree[r],r_res)l>>=1r>>=1return self.func(l_res,r_res)def max_right(self,l,f):assert 0<=l<=self.nassert f(self.ide)if l==self.n:return self.nl+=self.sizeres=self.idewhile True:while l&1==0:l>>=1if not f(self.func(res,self.tree[l])):while l<self.size:l*=2if f(self.func(res,self.tree[l])):res=self.func(res,self.tree[l])l+=1return l-self.sizeres=self.func(res,self.tree[l])l+=1if l&(-l)==l:breakreturn self.ndef min_left(self,r,f):assert 0<=r<=self.nassert f(self.ide)if r==0:return 0r+=self.sizeres=self.idewhile True:r-=1while r>1 and r&1:r>>=1if not f(self.func(self.tree[r],res)):while r<self.size:r=2*r+1if f(self.func(self.tree[r],res)):res=self.func(self.tree[r],res)r-=1return r+1-self.sizeres=self.func(self.tree[r],res)if r&(-r)==r:breakreturn 0def __getitem__(self,i):return self.get(i)def __setitem__(self,key,val):self.update(key,val)def __iter__(self):for i in range(self.n):yield self.tree[i+self.size]def __str__(self):return str(list(self))mod=998244353table_size=3*10**5fac=[1]*(table_size+1)finv=[1]*(table_size+1)for i in range(2,table_size+1):fac[i]=fac[i-1]*i%modfinv[table_size]=pow(fac[table_size],mod-2,mod)for i in range(table_size-1,-1,-1):finv[i]=finv[i+1]*(i+1)%moddef rebuild(n):global table_size,fac,finvfac+=[0]*(n-table_size)fac+=[0]*(n-table_size)finv+=[0]*(n-table_size)for i in range(table_size+1,n+1):fac[i]=fac[i-1]*i%modfinv[n]=inv(fac[n])for i in range(n-1,table_size,-1):finv[i]=finv[i+1]*(i+1)%modtable_size=ndef binom(n,k):if n<0 or k<0:return 0if k>n:return 0if n>table_size:rebuild(n+10**4)return (fac[n]*finv[k]%mod)*finv[n-k]%moddef fpow(x,k):res=1while k:if k&1:res=res*x%modx=x*x%modk>>=1return resdef inv(a):if a<table_size:return fac[a-1]*finv[a]%modreturn fpow(a,mod-2)n=int(input())p=list(map(lambda x:int(x)-1,input().split()))idx=[0]*nfor i in range(n):idx[p[i]]=ians=0def f(a,b):return binom(a+b,a)seg=segtree([0]*n,lambda x,y:x+y,0)for i in range(n):lu=seg.query(0,idx[i])ld=idx[i]-luru=seg.query(idx[i]+1,n)rd=n-1-idx[i]-ruans+=f(lu,rd)*f(ru,ld)ans%=modseg[idx[i]]=1print(ans)