結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー ts5208
提出日時 2025-09-06 14:38:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,762 ms / 2,500 ms
コード長 2,580 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 151,712 KB
最終ジャッジ日時 2025-09-06 14:39:26
合計ジャッジ時間 38,755 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)
    def add(self, index, value):
        index += 1 
        while index <= self.size:
            self.tree[index] += value
            index += index & -index
    def sum(self, index):
        index += 1
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result
    def range_sum(self, left, right):
        return self.sum(right - 1) - self.sum(left - 1)
from heapq import heappop, heappush, heapify
from bisect import bisect
#from sortedcontainers import SortedList
from collections import deque, defaultdict
from math import floor, ceil, isqrt, comb
from sys import stdin, setrecursionlimit
#setrecursionlimit(10**7)
intin = lambda: int(stdin.readline())
strin = lambda: stdin.readline().rstrip()
listin = lambda: list(map(int, stdin.readline().split()))
tuplein = lambda m: [tuple(map(lambda x: int(x) if x.isdigit() or (len(x) > 1 and x[0] == "-" and x[1:].isdigit()) else x, stdin.readline().split())) for _ in range(m)]
gridin = lambda m: [list(map(int, stdin.readline().split())) for _ in range(m)]
strgridin = lambda h: [stdin.readline().rstrip() for _ in range(h)]
mapin = lambda: map(int, stdin.readline().split())
N, M = mapin()
ALR = tuplein(N)
Q = intin()
XYUV = tuplein(Q)
SA = 0
SB = 0
imos = BIT(M + 1)
fenwick = BIT(M)
LR = [(0, 0) for _ in range(N)]
A = [0] * N
pos = [i for i in range(N)]
for i, (a, l, r) in enumerate(ALR):
    SA += (r - l + 1) * a
    imos.add(l-1, 1)
    imos.add(r, -1)
    LR[i] = (l, r)
    A[i] = a
    fenwick.add(i, a)
for i, (a, l, r) in enumerate(ALR):
    SB += a * imos.range_sum(0, i + 1)
for x, y, u, v in XYUV:
    #print(LR)
    x -= 1; y -= 1
    SA -= (LR[x][1] - LR[x][0] + 1) * A[x]
    SB -= fenwick.range_sum(LR[x][0]-1, LR[x][1])
    SB -= imos.range_sum(0, pos[x] + 1) * A[x]
    if LR[x][0] - 1 <= pos[x] <= LR[x][1] - 1:
        SB += A[x]
    #print(fenwick.range_sum(LR[x][0]-1, LR[x][1]), imos.range_sum(0, x + 1) * A[x])
    fenwick.add(pos[x], -A[x])
    imos.add(LR[x][0]-1, -1)
    imos.add(LR[x][1], 1)
    imos.add(u-1, 1)
    imos.add(v, -1)
    fenwick.add(y, A[x])
    LR[x] = (u, v)
    pos[x] = y
    SA += (v - u + 1) * A[x]
    SB += fenwick.range_sum(u-1, v)
    SB += imos.range_sum(0, y + 1) * A[x]
    if u - 1 <= y <= v - 1:
        SB -= A[x]
    #print(SA, SB)
    #tmpls = []
    #for i in range(M + 1):
    #    tmpls.append(imos.range_sum(0, i))
    #print(*tmpls)
    #print(SA, SB)
    print(SA-SB)
0