結果

問題 No.1433 Two color sequence
ユーザー raven7959
提出日時 2021-08-21 11:40:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 406 ms / 2,000 ms
コード長 1,637 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 145,888 KB
最終ジャッジ日時 2024-10-15 02:57:52
合計ジャッジ時間 9,404 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate
from math import inf
N=int(input())
S=input()
A=list(map(int,input().split()))
L=[0]*(N+1)
for i in range(N):
  if S[i]=="R":
    L[i+1]=A[i]
  else:
    L[i+1]=-A[i]
LA=list(accumulate(L))
class segtree():
  n=1
  size=1
  log=2
  d=[0]
  op=None
  e=10**15
  def update(self,k):
    self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
  def __init__(self,V,OP,E): #初期値(配列),演算,単位元で初期化
    self.n=len(V)
    self.op=OP
    self.e=E
    self.log=(self.n-1).bit_length()
    self.size=1<<self.log
    self.d=[E for i in range(2*self.size)]
    for i in range(self.n):
      self.d[self.size+i]=V[i]
    for i in range(self.size-1,0,-1):
      self.update(i)
  def set(self,p,x): #1点更新
    assert 0<=p and p<self.n
    p+=self.size
    self.d[p]=x
    for i in range(1,self.log+1):
      self.update(p>>i)
  def get(self,p): #1点取得
    assert 0<=p and p<self.n
    return self.d[p+self.size]
  def prod(self,l,r): #区間取得
    assert 0<=l and l<=r and r<=self.n
    sml=self.e
    smr=self.e
    l+=self.size
    r+=self.size
    while(l<r):
      if (l&1):
        sml=self.op(sml,self.d[l])
        l+=1
      if (r&1):
        smr=self.op(self.d[r-1],smr)
        r-=1
      l>>=1
      r>>=1
    return self.op(sml,smr)
  def all_prod(self): #全区間取得
    return self.d[1]
def MIN(x,y):
  return min(x,y)
def MAX(x,y):
  return max(x,y)
seg_min=segtree(LA,MIN,inf)
seg_max=segtree(LA,MAX,-inf)
ans_min=0
ans_max=0
for i in range(1,N+1):
  ans_min=min(ans_min,LA[i]-seg_max.prod(0,i))
  ans_max=max(ans_max,LA[i]-seg_min.prod(0,i))
print(max(-ans_min,ans_max))
0