結果
問題 | No.2520 L1 Explosion |
ユーザー |
![]() |
提出日時 | 2023-10-27 22:34:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 473 ms / 2,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 148,060 KB |
最終ジャッジ日時 | 2024-09-25 14:37:09 |
合計ジャッジ時間 | 7,099 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
n,m=map(int,input().split())M=998244353p=[]zx=[10**10]zy=[10**10]for i in range(n):x,y,h=map(int,input().split())p+=[(x-y,x+y,m-h)]zx+=[x-y-m+h]zx+=[x-y+m-h]zy+=[x+y-m+h]zy+=[x+y+m-h]zx=list(sorted(set(zx)))dx={v:i for i,v in enumerate(zx)}zy=list(sorted(set(zy)))dy={v:i for i,v in enumerate(zy)}q=[[0]*(len(zy)+1) for i in range(len(zx)+1)]for x,y,l in p:q[dx[x-l]][dy[y-l]]+=1q[dx[x+l]][dy[y-l]]-=1q[dx[x-l]][dy[y+l]]-=1q[dx[x+l]][dy[y+l]]+=1a=[0]*(n+1)for i in range(len(zx)-1):for j in range(len(zy)-1):q[i][j]+=q[i-1][j]+q[i][j-1]-q[i-1][j-1]a[q[i][j]]+=(zx[i+1]-zx[i])*(zy[j+1]-zy[j])%Ma[q[i][j]]%=Mfor v in a[1:]:print(v*pow(2,M-2,M)%M)