結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)