結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー Nikkuniku029
提出日時 2025-09-16 19:46:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,791 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-09-16 19:46:53
合計ジャッジ時間 4,869 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from atcoder.lazysegtree import LazySegTree


# 値の2項演算
def op(value1, value2):
    return [value1[0] + value2[0], value1[1] + value2[1]]


# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return [value[0], value[1] + f * value[0]]


# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return f + g


# 値の単位元
e = [0, 0]

# 作用素の単位元
id_ = 0

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(op, e, mapping, composition, id_, l)
B = LazySegTree(op, e, mapping, composition, id_, l2)
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.apply(l - 1, r, 1)
    ans += (r - l + 1) * a
    B.apply(i, i + 1, a)
res = 0
for i in range(M):
    temp = LST.prod(i, i + 1)[1] * B.get(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.prod(l_past - 1, r_past)[1]
    LST.apply(l_past - 1, r_past, -1)
    p = LST.get(now)[1]
    q = LST.get(y)[1]
    res -= b * p
    res += b * q
    B.apply(now, now + 1, -b)
    B.apply(y, y + 1, b)
    res += B.prod(u - 1, v)[1]
    LST.apply(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