結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー hotaru-ishibashi
提出日時 2025-09-18 15:52:23
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,447 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 67,960 KB
最終ジャッジ日時 2025-09-18 15:52:33
合計ジャッジ時間 9,438 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from atcoder.lazysegtree import LazySegTree
from atcoder.segtree import SegTree
N, M = map(int, input().split())

# 家iの寄与回数
house = LazySegTree(
    max, 
    -1, 
    lambda l, d: d + l, 
    lambda l1, l2: l1+l2,
    0,
    [0] * M
)

segs = [None] * N
# 人iの(レート, l, r, 家)
person = [None] * N
cur_sum = 0

for i in range(N):
    a, l, r = map(int, input().split())
    l -= 1
    person[i] = (a, l, r, i)
    segs[i] = (l, r)

house_rate = SegTree(lambda x, y:x+y, 0, [0 if i>=N else person[i][0] for i in range(M)])

for i, (l, r) in enumerate(segs):
    house.apply(l, r, 1)
    cur_sum += person[i][0] * (r-l)

for i in range(N):
    cur_sum -= house.get(i) * person[i][0]

# print(house, person, segs, cur_sum)
for _ in range(int(input())):
    x, y, newl, newr = map(lambda x:int(x)-1, input().split())
    newr += 1

    a, l, r, house_idx = person[x]
    # 元の寄与を消す
    cur_sum -= a * (r-l)

    cur_sum += house.get(house_idx) * a
    house.apply(l, r, -1)
    house_rate.set(house_idx, 0)
    cur_sum += house_rate.prod(l, r)
    
    # 新たな寄与を足す
    house_rate.set(y, a)
    cur_sum -= house.get(y) * a
    house.apply(newl, newr, 1)
    cur_sum += a * (newr - newl)
    cur_sum -= house_rate.prod(newl, newr)

    # print([house_rate.get(p) for p in range(M)])
    person[x] = (a, newl, newr, y)
    # print(person)
    # print([house.get(i) for i in range(M)])
    print(cur_sum)
0