結果
問題 | No.1996 <>< |
ユーザー |
![]() |
提出日時 | 2022-07-01 21:50:02 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,455 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 86,244 KB |
最終ジャッジ日時 | 2024-11-26 04:43:43 |
合計ジャッジ時間 | 12,729 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 WA * 2 |
ソースコード
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 debug(self,s=10):print([self.get(i) for i in range(min(self.n,s))])mod=10**9+7n,k=map(int,input().split())a=list(map(int,input().split()))s=input()b=list(range(n))b.sort(key=lambda x:n*a[x]+n-x)c=list(range(n))c.sort(key=lambda x:n*a[x]+n-x)c=c[::-1]def op(x,y):return (x+y)%moddp=[1]*nfor i in s:dpn=[0]*nseg=segtree([0]*n,op,0)if i=='<':for j in b:dpn[j]=seg.query(0,j)seg.update(j,dp[j])else:for j in c:dpn[j]=seg.query(0,j)seg.update(j,dp[j])dp=dpnprint(sum(dp)%mod)