結果
問題 |
No.1996 <><
|
ユーザー |
![]() |
提出日時 | 2024-10-16 11:39:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,700 ms / 2,000 ms |
コード長 | 742 bytes |
コンパイル時間 | 1,337 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 99,448 KB |
最終ジャッジ日時 | 2024-10-16 11:39:57 |
合計ジャッジ時間 | 21,751 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
n,K=map(int,input().split()) a=list(map(int,input().split())) z=[0,10**10]+a z=sorted(set(z)) d={v:i for i,v in enumerate(z)} for i in range(n): a[i]=d[a[i]] s=input() q=[[0]*(K+2) for i in range(n)] for i in range(n): q[i][1]=1 M=10**9+7 B=40 for j in range(2,K+2): st1=[0]*B*B st2=[0]*B for i in range(n): if s[j-2]=="<": l=0 r=a[i]-1 if s[j-2]==">": l=a[i]+1 r=len(z)-1 yl=l//B yr=r//B if yl==yr: q[i][j]+=sum(st1[l:r+1]) else: q[i][j]+=sum(st1[l:yl*B+B]) q[i][j]+=sum(st2[yl+1:yr]) q[i][j]+=sum(st1[yr*B:r+1]) q[i][j]%=M st1[a[i]]+=q[i][j-1] st1[a[i]]%=M st2[a[i]//B]+=q[i][j-1] st2[a[i]//B]%=M print(sum(q[i][K+1] for i in range(n))%M)