結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー ts5208
提出日時 2025-09-06 14:19:55
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,609 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 67,072 KB
最終ジャッジ日時 2025-09-06 14:20:10
合計ジャッジ時間 5,343 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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(M)]
A = [0] * M
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:
    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, x + 1) * A[x]
    if LR[x][0] - 1 <= 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(x, -A[x])
    imos.add(LR[x][0]-1, -1)
    imos.add(LR[x][1], 1)
    LR[x] = (0, 0)
    A[y] = A[x]
    A[x] = 0
    imos.add(u-1, 1)
    imos.add(v, -1)
    fenwick.add(y, A[y])
    LR[y] = (u, v)
    SA += (v - u + 1) * A[y]
    SB += fenwick.range_sum(u-1, v)
    SB += imos.range_sum(0, y + 1) * A[y]
    #print(SB, fenwick.range_sum(u-1, v), imos.range_sum(0, y + 1) * A[y])
    if u - 1 <= y <= v - 1:
        SB -= A[y]
    #print(SA, SB)
    #tmpls = []
    #for i in range(M + 1):
    #    tmpls.append(imos.range_sum(0, i))
    #print(*tmpls)
    print(SA-SB)
0