結果

問題 No.3116 More and more teleporter
ユーザー Koi
提出日時 2025-04-18 22:58:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 407 ms / 2,000 ms
コード長 1,932 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 81,872 KB
実行使用メモリ 90,764 KB
最終ジャッジ日時 2025-04-18 22:58:28
合計ジャッジ時間 7,025 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DualSegTree:
    def __init__(self,N,A,op,e) -> None:
        #N:数列の長さ
        #A:数列の初期状態
        #op:区間更新の写像
        #e:∀a,op(a,e)=aとなる単位元e
        size=1
        log_size=1
        while size<N:
            size*=2
            log_size+=1
        #size:セグ木の横の大きさ
        #log_size:セグ木の深さ(?)
        self.size=size
        self.log_size=log_size
        self.op=op
        self.e=e
        self.tree=[e for _ in range(2*size)]
        for i in range(N):
            self.tree[size+i]=A[i]
    
    #seg_treeを深さ順に出力
    #時間計算量O(N)
    def print_seg_tree(self):
        for i in range(self.log_size):
            print(self.tree[2**i:2**(i+1)])

    #Aのi番目(0-indexed)の要素を遅延とかを適用しながら取得する
    #時間計算量O(logN)
    def get(self,i):
        i+=self.size
        ans=self.tree[i]
        while i>1:
            i=i//2
            ans=self.op(ans,self.tree[i])
        return ans

    #Aの[l,r)をop(A[i],x)で更新する(実際にはせず遅延に色々する)
    #時間計算量O(logN)
    def update(self,l,r,x):
        l+=self.size
        r+=self.size
        while l<r:
            if(l%2==1):
                self.tree[l]=self.op(self.tree[l],x)
                l+=1
            if(r%2==1):
                self.tree[r-1]=self.op(self.tree[r-1],x)
                r-=1
            l=l//2
            r=r//2


N,Q=map(int,input().split())
DST0=DualSegTree(N,[0] * N, min, 10 ** 9)
DST1=DualSegTree(N,[N] * N, min, 10 ** 9)
ans=[]
for i in range(Q):
    query=list(map(int,input().split()))
    if(query[0]==1):
        x = query[1] - 1
        ans.append(min(x + DST0.get(x), N - 1 - x + DST1.get(x)))
    else:
        x = query[1] - 1
        c = query[2]
        DST0.update(x, N, c - x)
        DST1.update(0, x + 1, c - (N - 1 - x))
for a in ans:
    print(a)
0