結果
問題 | No.1996 <>< |
ユーザー | とりゐ |
提出日時 | 2022-07-01 21:52:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,072 ms / 2,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 87,020 KB |
実行使用メモリ | 87,460 KB |
最終ジャッジ日時 | 2023-08-17 09:25:04 |
合計ジャッジ時間 | 15,732 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,312 KB |
testcase_01 | AC | 71 ms
71,152 KB |
testcase_02 | AC | 74 ms
71,412 KB |
testcase_03 | AC | 93 ms
76,508 KB |
testcase_04 | AC | 72 ms
71,172 KB |
testcase_05 | AC | 71 ms
71,516 KB |
testcase_06 | AC | 72 ms
71,508 KB |
testcase_07 | AC | 73 ms
71,444 KB |
testcase_08 | AC | 117 ms
77,876 KB |
testcase_09 | AC | 86 ms
76,496 KB |
testcase_10 | AC | 117 ms
77,440 KB |
testcase_11 | AC | 614 ms
83,436 KB |
testcase_12 | AC | 1,043 ms
87,428 KB |
testcase_13 | AC | 1,051 ms
87,460 KB |
testcase_14 | AC | 1,072 ms
87,332 KB |
testcase_15 | AC | 923 ms
85,256 KB |
testcase_16 | AC | 802 ms
84,540 KB |
testcase_17 | AC | 909 ms
85,392 KB |
testcase_18 | AC | 627 ms
83,260 KB |
testcase_19 | AC | 696 ms
83,516 KB |
testcase_20 | AC | 660 ms
82,724 KB |
testcase_21 | AC | 836 ms
84,320 KB |
testcase_22 | AC | 936 ms
85,364 KB |
testcase_23 | AC | 170 ms
78,484 KB |
testcase_24 | AC | 606 ms
82,652 KB |
testcase_25 | AC | 367 ms
79,276 KB |
testcase_26 | AC | 545 ms
81,988 KB |
testcase_27 | AC | 222 ms
79,264 KB |
testcase_28 | AC | 90 ms
76,452 KB |
testcase_29 | AC | 363 ms
81,240 KB |
testcase_30 | AC | 133 ms
78,520 KB |
testcase_31 | AC | 236 ms
79,252 KB |
testcase_32 | AC | 127 ms
77,980 KB |
ソースコード
class segtree(): def __init__(self,init,func,ide): self.n=len(init) self.func=func self.ide=ide self.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.size self.tree[k]=x k>>=1 while k: self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1]) k>>=1 def get(self,i): return self.tree[i+self.size] def query(self,l,r): l+=self.size r+=self.size l_res=self.ide r_res=self.ide while l<r: if l&1: l_res=self.func(l_res,self.tree[l]) l+=1 if r&1: r-=1 r_res=self.func(self.tree[r],r_res) l>>=1 r>>=1 return 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+7 n,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]+x) c=c[::-1] def op(x,y):return (x+y)%mod dp=[1]*n for i in s: dpn=[0]*n seg=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=dpn print(sum(dp)%mod)