結果
問題 | No.2950 Max Min Product |
ユーザー |
![]() |
提出日時 | 2024-10-26 10:09:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,635 bytes |
コンパイル時間 | 597 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 242,340 KB |
最終ジャッジ日時 | 2024-10-26 10:11:20 |
合計ジャッジ時間 | 81,276 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 30 |
ソースコード
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):l+=self.tlr+=self.tlp=[]while l<=r:if l%2==1:yield ll+=1if r%2==0:yield rr-=1l//=2r//=2return pdef propa(self,l,r):l+=self.tlr+=self.tlwhile l>0:if l%2==1:breakl//=2while r>0:if r%2==0:breakr//=2p=[]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)for y in self.gindex(l,r):self.update(y,x)l+=self.tlr+=self.tlwhile l>0:if l%2==1:breakl//=2while r>0:if r%2==0:breakr//=2l//=2r//=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)a=0for i in self.gindex(l,r):a=self.op(a,self.st[i])return an=int(input())a=list(map(int,input().split()))+[0]#from random import randrange#n=200000#a=[randrange(1,10**9) for i in range(n)]+[0]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)