結果

問題 No.2697 Range LIS Query
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-10-02 20:33:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,492 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 280,376 KB
最終ジャッジ日時 2024-10-02 20:34:21
合計ジャッジ時間 23,383 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 324 ms
126,080 KB
testcase_01 AC 281 ms
125,696 KB
testcase_02 AC 347 ms
126,912 KB
testcase_03 AC 3,039 ms
270,152 KB
testcase_04 AC 2,933 ms
267,480 KB
testcase_05 AC 3,223 ms
269,448 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
a=list(map(int,input().split()))

B=317
st1=[[[0]*4,[0]*4,[0]*4,[0]*4] for i in range(B*B)]
st2=[[[0]*4,[0]*4,[0]*4,[0]*4] for i in range(B)]
lt=[0]*B

def op(x,y):
  z=[[0]*4,[0]*4,[0]*4,[0]*4]
  for xl in range(4):
    for xr in range(xl,4):
      for yl in range(xr,4):
        for yr in range(yl,4):
          z[xl][yr]=max(z[xl][yr],x[xl][xr]+y[yl][yr])
  return z

def mp(f,x):
  match f:
    case 0:
      return x
    case 1:
      return [[1,0,0,0],[0]*4,[0]*4,[0]*4]
    case 2:
      return [[0]*4,[0,1,0,0],[0]*4,[0]*4]
    case 3:
      return [[0]*4,[0]*4,[0,0,1,0],[0]*4]
    case 4:
      return [[0]*4,[0]*4,[0]*4,[0,0,0,1]]
  return

for i in range(n):
  st1[i]=mp(a[i],st1[i])
for i in range(B):
  for j in range(i*B,i*B+B):
    st2[i]=op(st2[i],st1[j])

Q=int(input())
for _ in range(Q):
  query=list(map(int,input().split()))
  t=query[0]
  if t==1:
    _,l,r=query
    l-=1
    r-=1
    yl=l//B
    yr=r//B
    for i in range(yl*B,yl*B+B):
      st1[i]=mp(lt[yl],st1[i])
    lt[yl]=0
    for i in range(yr*B,yr*B+B):
      st1[i]=mp(lt[yr],st1[i])
    lt[yr]=0
    a=[[0]*4,[0]*4,[0]*4,[0]*4]
    if yl==yr:
      for i in range(l,r+1):
        a=op(a,st1[i])
    else:
      for i in range(l,yl*B+B):
        a=op(a,st1[i])
      for i in range(yl+1,yr):
        a=op(a,st2[i])
      for i in range(yr*B,r+1):
        a=op(a,st1[i])
    print(max(a[0]+a[1]+a[2]+a[3]))
  else:
    _,l,r,x=query
    l-=1
    r-=1
    yl=l//B
    yr=r//B
    for i in range(yl*B,yl*B+B):
      st1[i]=mp(lt[yl],st1[i])
    lt[yl]=0
    for i in range(yr*B,yr*B+B):
      st1[i]=mp(lt[yr],st1[i])
    lt[yr]=0
    if yl==yr:
      for i in range(l,r+1):
        st1[i]=mp(x,st1[i])
      st2[yl]=[[0]*4,[0]*4,[0]*4,[0]*4]
      for i in range(yl*B,yl*B+B):
        st2[yl]=op(st2[yl],st1[i])
    else:
      for i in range(l,yl*B+B):
        st1[i]=mp(x,st1[i])
      st2[yl]=[[0]*4,[0]*4,[0]*4,[0]*4]
      for i in range(yl*B,yl*B+B):
        st2[yl]=op(st2[yl],st1[i])
      for i in range(yl+1,yr):
        match x:
          case 1:
            st2[i]=[[B,0,0,0],[0]*4,[0]*4,[0]*4]
          case 2:
            st2[i]=[[0]*4,[0,B,0,0],[0]*4,[0]*4]
          case 3:
            st2[i]=[[0]*4,[0]*4,[0,0,B,0],[0]*4]
          case 4:
            st2[i]=[[0]*4,[0]*4,[0]*4,[0,0,0,B]]
        lt[i]=x
      for i in range(yr*B,r+1):
        st1[i]=mp(x,st1[i])
      st2[yr]=[[0]*4,[0]*4,[0]*4,[0]*4]
      for i in range(yr*B,yr*B+B):
        st2[yr]=op(st2[yr],st1[i])
0