結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:20:24 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,611 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 77,292 KB |
最終ジャッジ日時 | 2025-09-06 14:20:31 |
合計ジャッジ時間 | 6,584 ms |
ジャッジサーバーID (参考情報) |
judge / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 TLE * 1 |
other | -- * 21 |
ソースコード
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)