結果
問題 | No.2520 L1 Explosion |
ユーザー |
|
提出日時 | 2023-10-04 23:37:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,250 ms / 2,000 ms |
コード長 | 923 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 79,484 KB |
最終ジャッジ日時 | 2024-07-26 14:55:00 |
合計ジャッジ時間 | 15,648 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
import sys, time, randomfrom collections import deque, Counter, defaultdictinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353n, m = mi()XYH = [li() for _ in range(n)]XYH = [[v[0] - v[1], v[0] + v[1],m - v[2]] for v in XYH]L = []for x, y, h in XYH:L.append((x - h, y - h, 1))L.append((x + h, y - h, -1))L.append((x - h, y + h, -1))L.append((x + h, y + h, 1))L.sort()a = [0] * (n + 1)ans = [0] * (n + 1)now = []nowx = -inffor x, y, c in L:if nowx != x:now.sort()cnt = 0bef = -inffor i in range(0, len(now)-1):cnt += now[i][1]ans[cnt] += (now[i + 1][0] - now[i][0]) * (x - nowx)nowx = xnow.append((y, c))for v in [v * pow(2, mod - 2, mod) % mod for v in ans[1:]]:print(v)