結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:08:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,314 ms / 2,500 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 462 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 185,588 KB |
最終ジャッジ日時 | 2025-09-06 14:09:12 |
合計ジャッジ時間 | 49,797 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
class BIT: def __init__(self, A): self.size = len(A) self.bit = [0]*(len(A)+1) for i in range(len(A)): self.add(i, A[i]) def sum(self, i): i += 1 ans = 0 while i > 0: ans += self.bit[i] i -= -i&i return ans def query(self, l, r): if l == 0: return self.sum(r-1) else: return self.sum(r-1)-self.sum(l-1) def add(self, i, x): i += 1 while i <= self.size: self.bit[i] += x i += -i&i def op(x, y): return x+y class SegTree: def __init__(self, init_val, op, ide_ele): n = len(init_val) self.n = n self.op = op self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num for i in range(n): self.tree[self.num + i] = init_val[i] def update(self, l, r, x): l += self.num r += self.num while l < r: if l & 1: self.tree[l] = self.op(x, self.tree[l]) l += 1 if r & 1: self.tree[r - 1] = self.op(x, self.tree[r - 1]) l >>= 1 r >>= 1 def query(self, k): ans = self.ide_ele k += self.num ans = self.op(ans, self.tree[k]) while k > 1: ans = self.op(ans, self.tree[k>>1]) k >>= 1 return ans N, M = map(int, input().split()) ALR = [list(map(int, input().split())) for _ in range(N)] Q = int(input()) query = [list(map(int, input().split())) for _ in range(Q)] segC = SegTree([0]*M, op, 0) F = BIT([0]*M) P = list(range(N)) LR = [[-1, -1] for _ in range(N)] for i, (A, L, R) in enumerate(ALR): L, R = L-1, R-1 LR[i] = [L, R] segC.update(L, R+1, 1) F.add(i, A) ans = 0 for i, (A, L, R) in enumerate(ALR): L, R = L-1, R-1 ans += A*(R-L+1)-F.query(L, R+1) for X, Y, U, V in query: X, Y, U, V = X-1, Y-1, U-1, V-1 L, R = LR[X] A = ALR[X][0] ans -= A*(R-L+1)-F.query(L, R+1) segC.update(L, R+1, -1) ans += A*segC.query(P[X]) F.add(P[X], -A) F.add(Y, A) ans += A*(V-U+1)-F.query(U, V+1) ans -= A*segC.query(Y) segC.update(U, V+1, 1) P[X] = Y LR[X] = [U, V] print(ans)