結果

問題 No.3265 地元に帰れば天才扱い!
ユーザー sasa8uyauya
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
0