結果
問題 | No.2950 Max Min Product |
ユーザー | sasa8uyauya |
提出日時 | 2024-10-26 09:28:22 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,812 bytes |
コンパイル時間 | 3,872 ms |
コンパイル使用メモリ | 81,768 KB |
実行使用メモリ | 251,184 KB |
最終ジャッジ日時 | 2024-10-26 09:29:52 |
合計ジャッジ時間 | 88,402 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
53,444 KB |
testcase_01 | AC | 35 ms
55,028 KB |
testcase_02 | AC | 37 ms
53,924 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | TLE | - |
testcase_29 | WA | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | AC | 2,620 ms
194,088 KB |
testcase_34 | AC | 1,756 ms
153,136 KB |
testcase_35 | AC | 2,416 ms
191,328 KB |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | AC | 35 ms
53,348 KB |
ソースコード
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):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)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]#from random import randrange#n=200000#a=[randrange(1,10**9) for i in range(n)]+[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)