結果

問題 No.3214 small square
ユーザー ゼット
提出日時 2025-08-04 21:43:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,660 ms / 3,000 ms
コード長 1,984 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 199,352 KB
最終ジャッジ日時 2025-08-04 21:44:17
合計ジャッジ時間 46,694 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree:
  def __init__(self,n):
    self.size=1
    self.height=0
    while self.size<n:
      self.size*=2
      self.height+=1
    self.dat=[0]*(self.size*2)                                      
    self.lazy=[0]*(self.size*2)
  def lazyup(self,l,r,a):
    l+=self.size
    r+=self.size
    while l<r:
      if l&1:
        self.lazy[l]+=a
        l+=1
      if r&1:
        r-=1
        self.lazy[r]+=a                              
      l//=2
      r//=2
  def querry(self,l,r):
    l+=self.size
    r+=self.size
    score=-10**10
    while l<r:
      if l&1:
        w=self.dat[l]+self.lazy[l]
        score=max(score,w)
        l+=1
      if r&1:
        r-=1
        w=self.dat[r]+self.lazy[r]
        score=max(score,w)
      l//=2
      r//=2
    return score
  def propagate(self,x):
    x+=self.size
    for h in range(self.height,0,-1):
      y=x>>h
      self.lazy[2*y]+=self.lazy[y]
      self.lazy[2*y+1]+=self.lazy[y]
      self.dat[y]+=self.lazy[y]
      self.lazy[y]=0
  def bottom(self,x):
    x+=self.size
    while x>1:
      x//=2
      self.dat[x]=max(self.dat[2*x]+self.lazy[2*x],self.dat[2*x+1]+self.lazy[2*x+1])
N,K=map(int,input().split())
Ax=set()
Ay=set()
Tx={}
Ty={}
L=[]
for i in range(N):
  x,y,w=map(int,input().split())
  L.append((2*x,2*y,w))
  Ax.add(2*x)
  Ay.add(2*y)
  Ax.add(2*x+2*K+1)
  Ay.add(2*y+2*K+1)
Ax=list(Ax)
Ay=list(Ay)
Ax.sort()
Ay.sort()
Mx=len(Ax)
My=len(Ay)
for i in range(Mx):
  Tx[Ax[i]]=i
for i in range(My):
  Ty[Ay[i]]=i
Gx=[[] for i in range(Mx)]
for i in range(N):
  x,y,w=L[i][:]
  px,py=Tx[x],Ty[y]
  px2,py2=Tx[x+2*K+1],Ty[y+2*K+1]
  Gx[px].append((py,+w))
  Gx[px].append((py2,-w))
  Gx[px2].append((py,-w))
  Gx[px2].append((py2,w))
result=0
Z=segtree(My)
for i in range(Mx):
  for B in Gx[i]:
    pos,w=B[:]
    Z.propagate(pos)
    Z.propagate(My-1)
    Z.lazyup(pos,My,w)
    Z.bottom(pos)
    Z.bottom(My-1)
  Z.propagate(0)
  Z.propagate(My-1)
  ans=Z.querry(0,My)
  result=max(result,ans)
print(result)
0