結果
問題 | No.2229 Treasure Searching Rod (Hard) |
ユーザー |
![]() |
提出日時 | 2023-02-24 22:10:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 614 ms / 2,000 ms |
コード長 | 1,354 bytes |
コンパイル時間 | 4,801 ms |
コンパイル使用メモリ | 266,500 KB |
最終ジャッジ日時 | 2025-02-10 21:14:40 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001using P = pair<mint,mint>;P op(P a,P b){a.first += b.first;a.second += b.second;return a;}P e(){return make_pair(0,0);}P mapping(mint a,P b){b.first += a*b.second;return b;}mint composition(mint a,mint b){return a+b;}mint id(){return 0;}int main(){int H,W,K;cin>>H>>W>>K;vector<P> t(300000,make_pair(0,1));vector<lazy_segtree<P,op,e,mint,mapping,composition,id>> seg(2,lazy_segtree<P,op,e,mint,mapping,composition,id>(t));int C = 100001;vector<vector<pair<int,long long>>> vs(C*2);rep(i,K){int x,y,z;cin>>x>>y>>z;x--,y--;vs[x-y+C].emplace_back(x+y,z);}mint ans = 0;rep(i,C*2){int tt = i-C;int L=max(tt,-tt),R = min(2*(W-1)+tt,2*(H-1)-tt);if(L<=R){seg[L%2].apply(L/2,R/2+1,1);}rep(j,vs[i].size()){int y = vs[i][j].first;mint vv = vs[i][j].second;mint s = 0;if(y%2==0){s += seg[0].prod(0,y/2+1).first;s += seg[1].prod(0,y/2).first;}else{s += seg[0].prod(0,y/2+1).first;s += seg[1].prod(0,y/2+1).first;}ans += vv * s;}}cout<<ans.val()<<endl;return 0;}