結果
問題 | No.2520 L1 Explosion |
ユーザー |
![]() |
提出日時 | 2023-10-27 22:59:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 2,521 bytes |
コンパイル時間 | 3,540 ms |
コンパイル使用メモリ | 286,444 KB |
実行使用メモリ | 38,784 KB |
最終ジャッジ日時 | 2024-09-25 14:59:59 |
合計ジャッジ時間 | 5,467 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using mint = modint998244353;template <class S>struct value_compression : vector<S> {bool built = false;using VS = vector<S>;using VS::VS;value_compression(vector<S> v) : vector<S>(move(v)) {}void build() {sort(this->begin(), this->end());this->erase(unique(this->begin(), this->end()), this->end());built = true;}template <class T>void convert(T first, T last) {assert(built);for (; first != last; ++first) *first = (*this)(*first);}int operator()(S x) {assert(built);return lower_bound(this->begin(), this->end(), x) - this->begin();}void clear() {this->clear();built = false;}};} int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;struct S {ll xl, xr, yl, yr;};vector<S> sq(n);rep(i, n) {ll x, y, h;cin >> x >> y >> h;ll rad = m - h;ll x1 = x - rad, y1 = y;ll x2 = x + rad, y2 = y;sq[i] = {x1 - y1, x2 - y2, x1 + y1, x2 + y2};}value_compression<ll> vcx, vcy;for (auto [xl, xr, yl, yr] : sq) {vcx.emplace_back(xl);vcx.emplace_back(xr);vcy.emplace_back(yl);vcy.emplace_back(yr);}vcx.build();vcy.build();int h = vcx.size(), w = vcy.size();VVI d(h, VI(w));for (auto [xl, xr, yl, yr] : sq) {xl = vcx(xl);xr = vcx(xr);yl = vcy(yl);yr = vcy(yr);d[xl][yl]++;d[xl][yr]--;d[xr][yl]--;d[xr][yr]++;}rep(i, h) rep(j, w - 1) d[i][j+1] += d[i][j];rep(i, h - 1) rep(j, w) d[i+1][j] += d[i][j];vector<mint> ans(n + 1);const mint inv2 = mint(2).inv();rep(i, h) rep(j, w) if (d[i][j]) {ans[d[i][j]] += mint(vcx[i+1] - vcx[i]) * (vcy[j+1] - vcy[j]) * inv2;}for (int i = 1; i <= n; i++) cout << ans[i].val() << '\n';}