結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー ゼット
提出日時 2025-09-06 13:44:16
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 1,851 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 308 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 161,156 KB
最終ジャッジ日時 2025-09-06 13:45:09
合計ジャッジ時間 47,073 ms
ジャッジサーバーID
（参考情報） 		judge / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 15 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class segtree:
  def __init__(self,n):
    self.size=1
    while self.size<n:
      self.size*=2
    self.dat=[0]*(self.size*2)
  def update(self,x,a):
    x+=self.size
    self.dat[x]=a
    while x>1:
      x//=2
      self.dat[x]=(self.dat[2*x]+self.dat[2*x+1])
  def querry(self,u,v):
    u+=self.size
    v+=self.size
    score=0
    while u<v:
      if u&1:
        score+=self.dat[u]
        u+=1
      if v&1:
        v-=1
        score+=self.dat[v]
      u//=2
      v//=2
    return score
class segtree2:
  def __init__(self,n):
    self.size=1
    while self.size<n:
      self.size*=2
    self.dat=[0]*(self.size*2)
  def update(self,x,a):
    x+=self.size
    self.dat[x]+=a
    while x>1:
      x//=2
      self.dat[x]=(self.dat[2*x]+self.dat[2*x+1])
  def querry(self,u,v):
    u+=self.size
    v+=self.size
    score=0
    while u<v:
      if u&1:
        score+=self.dat[u]
        u+=1
      if v&1:
        v-=1
        score+=self.dat[v]
      u//=2
      v//=2
    return score
N,M=map(int,input().split())
Zsum=segtree(M+2)
Zcount=segtree2(M+2)
L=[]
p=[0]*N
h=[[0]*2 for i in range(N)]
T=[0]*N
for i in range(N):
  a,l,r=map(int,input().split())
  Zsum.update(i+1,a)
  Zcount.update(l,1)
  Zcount.update(r+1,-1)
  L.append((a,l,r))
  p[i]=a
  h[i][0]=l
  h[i][1]=r
  T[i]=i+1
score=0
for i in range(N):
  a,l,r=L[i][:]
  score+=a*(r-l+1)-Zsum.querry(l,r+1)
Q=int(input())
for _ in range(Q):
  pos,y,c,d=map(int,input().split())
  pos-=1
  now=T[pos]
  a=p[pos]
  l,r=h[pos][:]
  h[pos][0]=c
  h[pos][1]=d
  score-=a*(r-l+1)-Zsum.querry(l,r+1)
  Zcount.update(l,-1)
  Zcount.update(r+1,1)
  count=Zcount.querry(0,now+1)
  score+=count*a
  Zsum.update(now,0)
  Zsum.update(y,a)
  score+=a*(d-c+1)-Zsum.querry(c,d+1)
  count=Zcount.querry(0,y+1)
  score-=count*a
  Zcount.update(c,1)
  Zcount.update(d+1,-1)
  T[pos]=y
  print(score)
0