結果
問題 | No.2251 Marking Grid |
ユーザー |
![]() |
提出日時 | 2023-03-17 23:16:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,307 ms / 3,000 ms |
コード長 | 1,277 bytes |
コンパイル時間 | 4,216 ms |
コンパイル使用メモリ | 261,288 KB |
最終ジャッジ日時 | 2025-02-11 14:20:52 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; int main(){ int h,w;cin>>h>>w; vector<vector<int>> a(h, vector<int>(w)); vector<ll> v(0); for (int i=0; i<h; i++){ for (int j=0; j<w; j++){ cin >> a[i][j]; v.push_back(((ll)a[i][j] << (ll)30) + (i<<15) + j); } } sort(v.begin(), v.end()); reverse(v.begin(), v.end()); ll mask = (1<<15) - 1; vector<int> x(h); dsu uf(w); int cnt = w; int cnth = h; vector<set<int>> hr(h); mint ans = 0; for (ll ty: v){ int j = ty & mask; int i = (ty>>15) & mask; mint val = ty >> 30; int tv = cnt + cnth - 2; int mode = 1; auto g = hr[i].lower_bound(j); if (g != hr[i].end()){ int k = *g; if (uf.same(k,j)) mode = 0; } if (g != hr[i].begin()){ g--; int k = *g; if (uf.same(k,j)) mode = 0; } if (mode == 1){ ans += mint(2).pow(tv) * val; } if (x[i] == 0){ x[i] = 1; cnth -= 1; } g = hr[i].lower_bound(j); if (g != hr[i].end()){ int k = *g; if (!uf.same(k,j)){ uf.merge(k,j); cnt-=1; } } if (g != hr[i].begin()){ g--; int k = *g; if (!uf.same(k,j)){ uf.merge(k,j); cnt-=1; } } hr[i].insert(j); } cout << ans.val() <<endl; }