結果

問題 No.2520 L1 Explosion
ユーザー titiatitia
提出日時 2023-11-01 01:56:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 398 ms / 2,000 ms
コード長 1,466 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 81,836 KB
実行使用メモリ 148,552 KB
最終ジャッジ日時 2023-11-01 01:57:05
合計ジャッジ時間 6,450 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,584 KB
testcase_01 AC 37 ms
53,584 KB
testcase_02 AC 36 ms
53,584 KB
testcase_03 AC 36 ms
53,584 KB
testcase_04 AC 36 ms
53,584 KB
testcase_05 AC 36 ms
53,584 KB
testcase_06 AC 393 ms
148,552 KB
testcase_07 AC 158 ms
83,612 KB
testcase_08 AC 398 ms
148,472 KB
testcase_09 AC 386 ms
148,440 KB
testcase_10 AC 392 ms
148,528 KB
testcase_11 AC 392 ms
148,528 KB
testcase_12 AC 395 ms
148,528 KB
testcase_13 AC 389 ms
148,440 KB
testcase_14 AC 390 ms
148,440 KB
testcase_15 AC 67 ms
70,656 KB
testcase_16 AC 302 ms
128,004 KB
testcase_17 AC 213 ms
107,936 KB
testcase_18 AC 217 ms
107,716 KB
testcase_19 AC 194 ms
104,124 KB
testcase_20 AC 54 ms
66,364 KB
testcase_21 AC 288 ms
124,356 KB
testcase_22 AC 79 ms
72,924 KB
testcase_23 AC 66 ms
70,656 KB
testcase_24 AC 250 ms
105,572 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