結果

問題 No.2520 L1 Explosion
コンテスト
ユーザー titia
提出日時 2023-11-01 01:56:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 400 ms / 2,000 ms
コード長 1,466 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 149,248 KB
最終ジャッジ日時 2024-09-25 17:50:51
合計ジャッジ時間 6,499 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

mod=998244353

N,M=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]

LIST=[]
LISTX=[]
LISTY=[]

for x,y,h in XY:
    x0=x+y
    y0=x-y
    
    if h<=M:
        k=M-h
        LIST.append([x0-k,y0-k,+1])
        LIST.append([x0+k,y0-k,-1])
        LIST.append([x0-k,y0+k,-1])
        LIST.append([x0+k,y0+k,+1])

        LISTX.append(x0-k)
        LISTX.append(x0+k)
        #LISTX.append(x0+k+1)

        LISTY.append(y0-k)
        LISTY.append(y0+k)
        #LISTY.append(y0+k+1)

LISTX=sorted(set(LISTX))
LISTY=sorted(set(LISTY))

#LISTX=list(range(-10,10))
#LISTY=list(range(-10,10))

DX={LISTX[i]:i for i in range(len(LISTX))}
DY={LISTY[i]:i for i in range(len(LISTY))}

for i in range(len(LIST)):
    LIST[i][0]=DX[LIST[i][0]]
    LIST[i][1]=DY[LIST[i][1]]

DP=[[0]*(len(LISTX)+4) for i in range(len(LISTX)+4)]

for x,y,h in LIST:
    DP[x][y]+=h

#print(LIST)
#for dp in DP:
#    print(*dp)

#print()

for i in range(len(LISTX)):
    for j in range(len(LISTY)):
        DP[i][j]+=DP[i-1][j]

for i in range(len(LISTX)):
    for j in range(len(LISTY)):
        DP[i][j]+=DP[i][j-1]
        
#for dp in DP:
#    print(*dp)

ANS=[0]*(N+1)

for i in range(len(LISTX)-1):
    for j in range(len(LISTY)-1):
        ANS[DP[i][j]]+=(LISTX[i+1]-LISTX[i])*(LISTY[j+1]-LISTY[j])
        #print(i,j,ANS)

INV=pow(2,mod-2,mod)
for i in range(1,len(ANS)):
    ANS[i]=ANS[i]*INV%mod
    print(ANS[i])
0