結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー ts5208
提出日時 2025-09-06 14:19:55
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 2,609 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 232 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 89,088 KB
最終ジャッジ日時 2026-07-14 20:07:42
合計ジャッジ時間 5,767 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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