結果

問題 No.2697 Range LIS Query
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-10-02 20:39:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,490 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 276,988 KB
最終ジャッジ日時 2024-10-02 20:40:21
合計ジャッジ時間 15,051 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
53,632 KB
testcase_01 AC 41 ms
53,376 KB
testcase_02 AC 65 ms
67,200 KB
testcase_03 AC 928 ms
134,192 KB
testcase_04 AC 944 ms
131,708 KB
testcase_05 AC 1,014 ms
148,292 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=int(n**0.5)+1
st1=[[[0]*4,[0]*3,[0]*2,[0]*1] for i in range(B*B)]
st2=[[[0]*4,[0]*3,[0]*2,[0]*1] for i in range(B)]
lt=[0]*B

def op(x,y):
  z=[[0]*4,[0]*3,[0]*2,[0]*1]
  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-xl]=max(z[xl][yr-xl],x[xl][xr-xl]+y[yl][yr-yl])
  return z

def mp(f,x):
  match f:
    case 0:
      return x
    case 1:
      return [[1,0,0,0],[0]*3,[0]*2,[0]*1]
    case 2:
      return [[0]*4,[1,0,0],[0]*2,[0]*1]
    case 3:
      return [[0]*4,[0]*3,[1,0],[0]*1]
    case 4:
      return [[0]*4,[0]*3,[0]*2,[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]*3,[0]*2,[0]*1]
    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]*3,[0]*2,[0]*1]
      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]*3,[0]*2,[0]*1]
      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]*3,[0]*2,[0]*1]
          case 2:
            st2[i]=[[0]*4,[B,0,0],[0]*2,[0]*1]
          case 3:
            st2[i]=[[0]*4,[0]*3,[B,0],[0]*1]
          case 4:
            st2[i]=[[0]*4,[0]*3,[0]*2,[B]]
        lt[i]=x
      for i in range(yr*B,r+1):
        st1[i]=mp(x,st1[i])
      st2[yr]=[[0]*4,[0]*3,[0]*2,[0]*1]
      for i in range(yr*B,yr*B+B):
        st2[yr]=op(st2[yr],st1[i])
0