結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー sasa8uyauya
提出日時 2025-09-06 15:41:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,799 bytes
コンパイル時間 324 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 94,696 KB
最終ジャッジ日時 2025-09-06 15:41:09
合計ジャッジ時間 7,186 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

B=448

class LST:
  def __init__(self):
    self.st1=[0]*B*B
    self.st2=[0]*B
    self.st3=[0]*B
    return
  
  def update(self,l,r):
    r-=1
    yl=l//B
    yr=r//B
    for y in [yl,yr]:
      for i in range(y*B,y*B+B):
        self.st1[i]+=self.st3[y]
      self.st3[y]=0
    return
  
  def apply(self,l,r,x):
    if l==r:
      return
    self.update(l,r)
    r-=1
    yl=l//B
    yr=r//B
    if yl==yr:
      for i in range(l,r+1):
        self.st1[i]+=x
        self.st2[yl]+=x
    else:
      for i in range(l,yl*B+B):
        self.st1[i]+=x
        self.st2[yl]+=x
      for i in range(yr*B,r+1):
        self.st1[i]+=x
        self.st2[yr]+=x
      for i in range(yl+1,yr):
        self.st2[i]+=x*B
        self.st3[i]+=x
    return
  
  def prod(self,l,r):
    if l==r:
      return 0
    self.update(l,r)
    r-=1
    yl=l//B
    yr=r//B
    a=0
    if yl==yr:
      a+=sum(self.st1[l:r+1])
    else:
      a+=sum(self.st1[l:yl*B+B])
      a+=sum(self.st1[yr*B:r+1])
      a+=sum(self.st2[yl+1:yr])
    return a


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=LST()
st2=LST()
for x in range(n):
  st1.apply(b[x],b[x]+1,a[x])
  st2.apply(l[x],r[x]+1,1)
g=0
for x in range(n):
  g+=(r[x]-l[x]+1)*a[x]-st1.prod(l[x],r[x]+1)
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.prod(l[x],r[x]+1)
  g-=-(st2.prod(b[x],b[x]+1)-(l[x]<=b[x]<=r[x]))*a[x]
  st1.apply(b[x],b[x]+1,-a[x])
  st2.apply(l[x],r[x]+1,-1)
  b[x]=y
  l[x],r[x]=nl,nr
  st1.apply(b[x],b[x]+1,a[x])
  st2.apply(l[x],r[x]+1,1)
  g+=(r[x]-l[x]+1)*a[x]-st1.prod(l[x],r[x]+1)
  g+=-(st2.prod(b[x],b[x]+1)-(l[x]<=b[x]<=r[x]))*a[x]
  print(g)
0