結果

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

ソースコード

diff # 

def segfunc(x, y):
    return x + y


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def add(self, k, x):
        k += self.num
        self.tree[k] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


class LazySegTree_RAQ:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def gindex(self, l, r):
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()
        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v == 0:
                continue
            self.lazy[i] = 0
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.tree[2 * i] += v
            self.tree[2 * i + 1] += v

    def add(self, l, r, x):
        ids = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.tree[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.tree[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = (
                self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) + self.lazy[i]
            )

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


N, M = map(int, input().split())
Ranges = [[-1, -1, 0] for _ in range(N)]
ans = 0
covered = [0] * (M + 1)
rates = [0] * (M + 1)
Index = [i for i in range(N)]
# 区間和取得の場合は[区間のサイズ, 値]として扱う
l = [[1, value] for value in covered]
l2 = [[1, value] for value in rates]
LST = LazySegTree_RAQ(covered, segfunc, 0)
B = SegTree(rates, segfunc, 0)
for i in range(N):
    a, l, r = map(int, input().split())
    Ranges[i][0] = l
    Ranges[i][1] = r
    Ranges[i][2] = a
    LST.add(l - 1, r, 1)
    ans += (r - l + 1) * a
    B.update(i, a)
res = 0
for i in range(M):
    temp = LST.query(i, i + 1) * B.query(i, i + 1)
    res += temp
Q = int(input())
answer = []
for _ in range(Q):
    x, y, u, v = map(int, input().split())
    x -= 1
    y -= 1
    now = Index[x]
    b = Ranges[x][2]
    l_past, r_past = Ranges[x][:2]
    res -= B.query(l_past - 1, r_past)
    LST.add(l_past - 1, r_past, -1)
    p = LST.query(now, now + 1)
    q = LST.query(y, y + 1)
    res -= b * p
    res += b * q
    B.update(now, 0)
    B.update(y, b)
    res += B.query(u - 1, v)
    LST.add(u - 1, v, 1)
    ans += ((v - u) - (r_past - l_past)) * b
    Ranges[x][0] = u
    Ranges[x][1] = v
    Index[x] = y
    answer.append(ans - res)
print(*answer, sep="\n")
0