結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
![]() |
提出日時 | 2025-09-06 16:08:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,810 ms / 2,500 ms |
コード長 | 1,157 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,900 KB |
実行使用メモリ | 90,884 KB |
最終ジャッジ日時 | 2025-09-06 16:08:51 |
合計ジャッジ時間 | 41,476 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
class BIT: def __init__(self,size): self.n=size self.tree=[0]*(self.n+1) def add(self,i,delta): i+=1 while i<=self.n: self.tree[i]+=delta i+=i&-i def _sum(self,i): i+=1 res=0 while i>0: res+=self.tree[i] i-=i&-i return res def sum(self,left,right): return self._sum(right)-self._sum(left-1) if left>0 else self._sum(right) n,m=map(int,input().split()) a=[0]*n b=[0]*n l=[0]*n r=[0]*n for i in range(n): a[i],l[i],r[i]=map(int,input().split()) l[i]-=1 r[i]-=1 b[i]=i st1=BIT(m) st2=BIT(m+1) for x in range(n): st1.add(b[x],a[x]) st2.add(l[x],1) st2.add(r[x]+1,-1) g=0 for x in range(n): g+=(r[x]-l[x]+1)*a[x]-st1.sum(l[x],r[x]) Q=int(input()) for _ in range(Q): x,y,nl,nr=map(int,input().split()) x-=1 y-=1 nl-=1 nr-=1 g-=(r[x]-l[x]+1)*a[x]-st1.sum(l[x],r[x]) g-=-(st2.sum(0,b[x])-(l[x]<=b[x]<=r[x]))*a[x] st1.add(b[x],-a[x]) st2.add(l[x],-1) st2.add(r[x]+1,1) b[x]=y l[x],r[x]=nl,nr st1.add(b[x],a[x]) st2.add(l[x],1) st2.add(r[x]+1,-1) g+=(r[x]-l[x]+1)*a[x]-st1.sum(l[x],r[x]) g+=-(st2.sum(0,b[x])-(l[x]<=b[x]<=r[x]))*a[x] print(g)