結果

問題 No.2697 Range LIS Query
コンテスト
ユーザー sasa8uyauya
提出日時 2024-10-02 20:38:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,480 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 268,804 KB
最終ジャッジ日時 2024-10-02 20:38:39
合計ジャッジ時間 22,126 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

B=317
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