結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー Sinonen
提出日時 2025-09-06 14:05:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,768 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 139,640 KB
最終ジャッジ日時 2025-09-06 14:05:20
合計ジャッジ時間 6,570 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self, op, e, n, v=None):
        self._n = n
        self._op = op
        self._e = e
        self._log = (n - 1).bit_length()
        self._size = 1 << self._log
        self._d = [self._e] * (2 * self._size)
        if v is not None:
            for i in range(self._n):
                self._d[self._size + i] = v[i]
            for i in range(self._size - 1, 0, -1):
                self._update(i)
    
    def set(self, p, x):
        assert 0 <= p < self._n
        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)
    
    def get(self, p):
        assert 0 <= p < self._n
        return self._d[p + self._size]
 
    def prod(self, l, r):
        assert 0 <= l <= r <= self._n
        sml, smr = self._e, self._e
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                sml = self._op(sml, self._d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self._op(self._d[r], smr)
            l >>= 1
            r >>= 1
        return self._op(sml, smr)
    
    def all_prod(self):
        return self._d[1]
 
    def _update(self, k):
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
#https://qiita.com/AkariLuminous/items/32cbf5bc3ffb2f84a898

def ADD(a, b):
	return a + b

N, M = list(map(int,input().split()))

Data = []
for i in range(N):
	a = list(map(int,input().split()))
	a[1] -= 1
	a[2] -= 1
	a.append(i)
	Data.append(a)
	
Count = SegTree(ADD, 0, M + 1)

Rate = SegTree(ADD, 0, M)

ans = 0
for i in range(N):
	Rate.set(i, Data[i][0])
	Count.set(Data[i][1], Count.get(Data[i][1]) + 1)
	Count.set(Data[i][2] + 1, Count.get(Data[i][2] + 1) -1)
	ans += Data[i][0] * (Data[i][2] - Data[i][1] + 1)
	
for i in range(N):
	ans -= Rate.prod(Data[i][1], Data[i][2] + 1)
Q = int(input())	
for _ in range(Q):
	x, y, u, v = list(map(int,input().split()))
	x -= 1
	y -= 1
	u -= 1
	v -= 1
	ans -= Data[x][0] * (Data[x][2] - Data[x][1] + 1)
	p = Count.prod(0, Data[x][3] + 1)
	ans += Data[x][0] * p
	if Data[x][1] <= Data[x][3] <= Data[x][2]:
		ans -= Data[x][0]
	ans += Rate.prod(Data[x][1], Data[x][2] + 1)
	Count.set(Data[x][1], Count.get(Data[x][1]) - 1)
	Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) + 1)
	Rate.set(Data[x][3], 0)
	Data[x][1] = u
	Data[x][2] = v
	Data[x][3] = y
	ans += Data[x][0] * (Data[x][2] - Data[x][1] + 1)
	Count.set(Data[x][1], Count.get(Data[x][1]) + 1)
	Count.set(Data[x][2] + 1, Count.get(Data[x][2] + 1) - 1)
	Rate.set(Data[x][3], Data[x][0])
	p = Count.prod(0, Data[x][3] + 1)
	ans -= Data[x][0] * p
	if Data[x][1] <= Data[x][3] <= Data[x][2]:
		ans += Data[x][0]
	ans -= Rate.prod(Data[x][1], Data[x][2] + 1)
	print(ans)
0