結果

問題 No.3094 Stapler
ユーザー titia
提出日時 2025-05-29 04:15:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,356 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 138,492 KB
最終ジャッジ日時 2025-05-29 04:16:40
合計ジャッジ時間 43,579 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N=int(input())
Q=int(input())

# 非再帰遅延伝搬セグ木（範囲更新, 範囲和出力）
# 高々N点を更新

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeのたかさ
SEG=[0]*(4*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def updates(l,r,x): # 区間[l,r)を+x更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]+=LAZY[ind]
            LAZY[1+(ind<<1)]+=LAZY[ind]
            
            SEG[(ind<<1)*2]+=update_lazy
            SEG[(ind<<1)*2+1]=max(SEG[(ind<<1)*2],0)
            SEG[(1+(ind<<1))*2]+=update_lazy
            SEG[(1+(ind<<1))*2+1]=max(SEG[(1+(ind<<1))*2],0)
    
            LAZY[ind]=0

    while L!=R:
        if L > R:
            SEG[2*L]+=x * (1<<(seg_height - (L.bit_length())))
            SEG[2*L+1]=max(SEG[2*L],0)
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[2*R]+=x * (1<<(seg_height - (R.bit_length())))
            SEG[2*R+1]=max(SEG[2*R],0)
            LAZY[R]+=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind*2]=SEG[(ind<<1)*2]+SEG[(1+(ind<<1))*2]
        SEG[ind*2+1]=SEG[(ind<<1)*2+1]+SEG[(1+(ind<<1))*2+1]

def getvalues(l,r): # 区間[l,r)に関する和を調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]+=LAZY[ind]
            LAZY[1+(ind<<1)]+=LAZY[ind]
            
            SEG[(ind<<1)*2]+=update_lazy
            SEG[(ind<<1)*2+1]=max(SEG[(ind<<1)*2],0)
            SEG[(1+(ind<<1))*2]+=update_lazy
            SEG[(1+(ind<<1))*2+1]=max(SEG[(1+(ind<<1))*2],0)
    
            LAZY[ind]=0
            
    ANS=0

    while L!=R:
        if L > R:
            ANS+=SEG[2*L+1]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS+=SEG[2*R+1]
            R//=(R & (-R))

    return ANS

for i in range(N):
    updates(i,i+1,1)

#ANS=getvalues(0,N-1)+1

#print(ANS)

Queries=[list(map(int,input().split())) for i in range(Q)]

for L in Queries:
    #print(SEG)
    if L[0]==3:
        ANS=getvalues(0,N-1)+1

        print(ANS)
    elif L[0]==2:
        x=L[1]-1
        l,r=Queries[x][1:]
        updates(l-1,r-1,1)
    else:
        l,r=L[1:]
        updates(l-1,r-1,-1)
    
        #ANS=getvalues(0,N-2)+1

        #print(l,r,ANS)
0