結果
問題 | No.2520 L1 Explosion |
ユーザー |
|
提出日時 | 2023-10-27 22:07:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 1,388 bytes |
コンパイル時間 | 1,256 ms |
コンパイル使用メモリ | 89,148 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-25 14:12:40 |
合計ジャッジ時間 | 2,137 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cassert>#include<atcoder/modint>using namespace std;using mint=atcoder::modint998244353;int N,M;int add[3000],cnt[3000];mint ans[1501];mint Yd[3000];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>M;vector<long>Ys;Ys.reserve(2*N);vector<pair<long,pair<long,bool> > >Xs;Xs.reserve(4*N);for(int i=0;i<N;i++){int X,Y,H;cin>>X>>Y>>H;long x=X+Y,y=X-Y;long d=M-H;Ys.push_back(y-d);Ys.push_back(y+d);Xs.push_back(make_pair(x-d,make_pair(y-d,true)));Xs.push_back(make_pair(x-d,make_pair(y+d,false)));Xs.push_back(make_pair(x+d,make_pair(y-d,false)));Xs.push_back(make_pair(x+d,make_pair(y+d,true)));}sort(Ys.begin(),Ys.end());Ys.erase(unique(Ys.begin(),Ys.end()),Ys.end());for(int j=0;j+1<Ys.size();j++)Yd[j]=Ys[j+1]-Ys[j];sort(Xs.begin(),Xs.end());for(int i=0;;){long nowX=Xs[i].first;for(int k=0;k<Ys.size();k++)add[k]=0;while(i<Xs.size()&&Xs[i].first==nowX){int y=lower_bound(Ys.begin(),Ys.end(),Xs[i].second.first)-Ys.begin();add[y]+=Xs[i].second.second?1:-1;i++;}if(i==Xs.size())break;mint dx=Xs[i].first-nowX;for(int k=0;k+1<Ys.size();k++){add[k+1]+=add[k];cnt[k]+=add[k];ans[cnt[k]]+=dx*Yd[k];}}const mint inv2=mint(1)/2;for(int i=1;i<=N;i++)cout<<(ans[i]*inv2).val()<<"\n";}