結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー 👑 SPD_9X2
提出日時 2025-09-13 01:33:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,228 bytes
コンパイル時間 548 ms
コンパイル使用メモリ 82,692 KB
実行使用メモリ 151,912 KB
最終ジャッジ日時 2025-09-13 01:34:41
合計ジャッジ時間 13,318 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 12 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

class RangeBIT:

    def __init__(self,N,indexed): #0-indexed or 1-indexed 指定可能
        self.bit1 = [0] * (N+2)
        self.bit2 = [0] * (N+2)
        self.mode = indexed

    def bitadd(self,a,w,bit): #aにwを加える(1-origin)
 
        x = a
        while x <= (len(bit)-1):
            bit[x] += w
            x += x & (-1 * x)
 
    def bitsum(self,a,bit): #ind 1～aまでの和を求める
 
        ret = 0
        x = a
        while x > 0:
            ret += bit[x]
            x -= x & (-1 * x)
        return ret
    
    def add(self,l,r,w): #半開区間[l,r)にwを加える

        l = l + (1-self.mode)
        r = r + (1-self.mode)
        self.bitadd(l,-1*w*l,self.bit1)
        self.bitadd(r,w*r,self.bit1)
        self.bitadd(l,w,self.bit2)
        self.bitadd(r,-1*w,self.bit2)

    def sum(self,l,r): #半開区間[l,r)の区間和

        l = l + (1-self.mode)
        r = r + (1-self.mode)
        ret =  self.bitsum(r,self.bit1) + r * self.bitsum(r,self.bit2)
        ret -= self.bitsum(l,self.bit1) + l * self.bitsum(l,self.bit2)

        return ret

import sys

N,M = map(int,input().split())
BitSum = RangeBIT(M,0)
BitLR = RangeBIT(M,0)

ApLR = []
for i in range(N):
    A,L,R = map(int,input().split())
    L -= 1
    R -= 1
    BitSum.add(i,i+1,A)
    ApLR.append( (A,i,L,R) )
    BitLR.add(L,R+1,1)

ans = 0
for i in range(N):
    A,p,L,R = ApLR[i]
    ans += (R-L+1) * A - BitSum.sum(L,R+1)

#print (ans,file=sys.stderr)

Q = int(input())
ANS = []

for _ in range(Q):

    i,Y,U,V = map(int,input().split())
    i -= 1
    Y -= 1
    U -= 1
    V -= 1

    # 削除
    A,p,L,R = ApLR[i]
    BitLR.add(L,R+1,-1)
    ans -= (R-L+1) * A - BitSum.sum(L,R+1)
    #print ((R-L+1) * A - BitSum.sum(L,R+1),file=sys.stderr)
    ans -= -1 * BitLR.sum(p,p+1) * A
    #print (-1 * BitLR.sum(p,p+1) * A,file=sys.stderr)
    BitSum.add(p,p+1,-A)


    # 追加
    ApLR[i] = (A,Y,U,V)
    A,p,L,R = ApLR[i]
    BitLR.add(L,R+1,1)
    ans += (R-L+1) * A - BitSum.sum(L,R+1)
    #print ((R-L+1) * A - BitSum.sum(L,R+1),file=sys.stderr)
    ans += -1 * BitLR.sum(p,p+1) * A
    #print (-1 * BitLR.sum(p,p+1) * A,file=sys.stderr)
    BitSum.add(p,p+1,A)

    ANS.append(ans)

print (*ANS,sep="\n")
0