結果

問題 No.2520 L1 Explosion
ユーザー titiatitia
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,224 KB
testcase_01 AC 37 ms
52,480 KB
testcase_02 AC 38 ms
52,224 KB
testcase_03 AC 38 ms
52,736 KB
testcase_04 AC 38 ms
52,480 KB
testcase_05 AC 39 ms
52,224 KB
testcase_06 AC 394 ms
148,788 KB
testcase_07 AC 162 ms
84,136 KB
testcase_08 AC 400 ms
149,112 KB
testcase_09 AC 390 ms
148,864 KB
testcase_10 AC 394 ms
149,120 KB
testcase_11 AC 394 ms
149,248 KB
testcase_12 AC 397 ms
148,752 KB
testcase_13 AC 394 ms
148,972 KB
testcase_14 AC 392 ms
148,736 KB
testcase_15 AC 65 ms
68,992 KB
testcase_16 AC 306 ms
128,096 KB
testcase_17 AC 217 ms
108,416 KB
testcase_18 AC 222 ms
107,832 KB
testcase_19 AC 198 ms
104,656 KB
testcase_20 AC 55 ms
64,896 KB
testcase_21 AC 294 ms
124,448 KB
testcase_22 AC 78 ms
73,600 KB
testcase_23 AC 68 ms
69,888 KB
testcase_24 AC 256 ms
105,548 KB
権限があれば一括ダウンロードができます

ソースコード

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