結果

問題 No.2992 Range ABCD String Query
コンテスト
ユーザー むつある
提出日時 2024-12-17 01:11:50
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,065 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 67,964 KB
最終ジャッジ日時 2024-12-17 01:11:56
合計ジャッジ時間 4,834 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

from atcoder.segtree import SegTree

n,q=map(int,input().split())
s=input()
#0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9
#AA,AB,AC,AD,BB,BC,BD,CC,CD,DD]

def base(x):
  if x=='A':
    return (0,n,n,n,1,n,n,1,n,1)
  elif x=='B':
    return (1,n,n,n,0,n,n,1,n,1)
  elif x=='C':
    return (1,n,n,n,1,n,n,0,n,1)
  else:
    return (1,n,n,n,1,n,n,1,n,0)

v=[]
for i in range(n):
  v.append(base(s[i]))
  
def f(x,y):
  if not x:
    return y
  if not y:
    return x

  C_D=min(y[8],y[9])
  B_D=min(y[6],C_D)
  A_D=min(y[3],B_D)
  B_C=min(y[5],y[7])
  A_C=min(y[2],B_C)
  A_B=min(y[0],y[1])
  
  AA=x[0]+y[0]
  AB=min(x[0]+A_B,x[1]+y[4])
  AC=min(x[0]+A_C,x[1]+B_C,x[2]+x[7])
  AD=min(x[0]+A_D,x[1]+B_D,x[2]+C_D,x[3]+y[9])
  BB=x[4]+y[4]
  BC=min(x[4]+B_C,x[5]+y[7])
  BD=min(x[4]+B_D,x[5]+C_D,x[6]+y[9])
  CC=x[7]+y[7]
  CD=min(x[7]+C_D,x[8]+y[9])
  DD=x[9]+y[9]
  return (AA,AB,AC,AD,BB,BC,BD,CC,CD,DD)

seg=SegTree(f,0,v)

for _ in range(q):
  x=input().split()
  if x[0]=='1':
    seg.set(int(x[1])-1,base(x[2]))
  else:
    l,r=int(x[1])-1,int(x[2])
    print(min(seg.prod(l,r)))
0