結果
問題 | No.2950 Max Min Product |
ユーザー |
![]() |
提出日時 | 2024-10-26 08:58:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,624 bytes |
コンパイル時間 | 367 ms |
コンパイル使用メモリ | 82,668 KB |
実行使用メモリ | 251,484 KB |
最終ジャッジ日時 | 2024-10-26 08:59:53 |
合計ジャッジ時間 | 90,564 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 WA * 26 TLE * 7 |
ソースコード
M=998244353class LazySegTree:def __init__(self,n):self.tl=1while self.tl<n:self.tl*=2self.st=[0]*self.tl+[1]*self.tlfor i in reversed(range(1,self.tl)):self.st[i]=self.op(self.st[i*2],self.st[i*2+1])self.lt=[1]*self.tl*2returndef op(self,x,y):return (x+y)%Mdef mp(self,f,x):return f*x%Mdef cp(self,g,f):return g*f%Mdef update(self,y,c):self.st[y]=self.mp(c,self.st[y])self.lt[y]=self.cp(c,self.lt[y])returndef gindex(self,l,r,f):l+=self.tlr+=self.tlpl=[]pr=[]while l<=r:if l%2:pl+=[l]l+=1if r%2==0:pr+=[r]r-=1l//=2r//=2if f:p=pl+pr[::-1]else:pl=pl[::-1]pr=pr[::-1]p=[]while len(pl)>0 and len(pr)>0:p+=[pl.pop(),pr.pop()]p+=pl[::-1]+pr[::-1]return pdef propa(self,l,r):p=self.gindex(l,r,1)l,r=p[0],p[-1]p=[]while l>0:p+=[l]l//=2while r>0:p+=[r]r//=2while len(p)>0:y=p.pop()if y*2<self.tl*2:self.update(y*2,self.lt[y])self.update(y*2+1,self.lt[y])self.lt[y]=1returndef apply(self,l,r,x):self.propa(l,r)p=self.gindex(l,r,0)d=[]while len(p)>0:y=p.pop()self.update(y,x)p=self.gindex(l,r,1)l,r=p[0]//2,p[-1]//2while l>0:self.st[l]=self.op(self.st[l*2],self.st[l*2+1])l//=2while r>0:self.st[r]=self.op(self.st[r*2],self.st[r*2+1])r//=2returndef prod(self,l,r):self.propa(l,r)p=self.gindex(l,r,1)a=0for i in p:a=self.op(a,self.st[i])return an=int(input())a=list(map(int,input().split()))+[0]M=998244353q=[(a[i],i) for i in range(n)]q.sort()w=[[0,0] for i in range(n)]p=[[] for i in range(n+1)]X=10**10a[-1]=Xql=[-1]for i in range(n):while a[ql[-1]]<a[i]:ql.pop()w[i][0]=ql[-1]+1ql+=[i]qr=[n]for i in reversed(range(n)):while a[qr[-1]]<a[i]:qr.pop()w[i][1]=qr[-1]-1qr+=[i]for i in range(n):v=a[i]l,r=w[i]p[i]+=[(l,i,v)]p[r+1]+=[(l,i,pow(v,M-2,M))]a[-1]=-Xql=[-1]for i in range(n):while a[ql[-1]]>a[i]:ql.pop()w[i][0]=ql[-1]+1ql+=[i]qr=[n]for i in reversed(range(n)):while a[qr[-1]]>a[i]:qr.pop()w[i][1]=qr[-1]-1qr+=[i]for i in range(n):v=a[i]l,r=w[i]p[i]+=[(l,i,v)]p[r+1]+=[(l,i,pow(v,M-2,M))]ans=0st=LazySegTree(n)for y in range(n):for l,r,v in p[y]:st.apply(l,r,v)l=0r=yans+=st.prod(l,r)ans%=Mprint(ans)