結果
問題 | No.2950 Max Min Product |
ユーザー |
|
提出日時 | 2024-10-22 20:41:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 395 ms / 3,000 ms |
コード長 | 1,031 bytes |
コンパイル時間 | 5,865 ms |
コンパイル使用メモリ | 322,944 KB |
実行使用メモリ | 16,132 KB |
最終ジャッジ日時 | 2024-10-25 23:29:31 |
合計ジャッジ時間 | 18,101 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using mint=modint998244353; struct S{ mint sum; int len; }; S op(S x,S y){ return {x.sum+y.sum,x.len+y.len}; } S e(){ return {0,0}; } S mapping(int f,S x){ if(f==-1)return x; return {mint(x.len)*f,x.len}; } int composition(int f,int g){ if(f==-1)return g; return f; } int id(){ return -1; } int main(){ int N;cin>>N; vector<int> A(N);for(auto&&e:A)cin>>e; stack<pair<int,int>> inc,dec; lazy_segtree<S,op,e,int,mapping,composition,id> seg_inc(N),seg_dec(N); mint ans=0,sum=0; for(int i=0;i<N;i++){ for(int j=0;j<2;j++){ int incl=i; while(inc.size()&&(inc.top().first<=A[i])^j){ auto[x,l]=inc.top();inc.pop(); sum-=x*seg_dec.prod(l,incl).sum; incl=l; } inc.push({A[i],incl}); seg_inc.apply(incl,i,A[i]); sum+=A[i]*seg_dec.prod(incl,i).sum; seg_inc.set(i,{A[i],1}); swap(inc,dec); swap(seg_inc,seg_dec); } sum+=mint(A[i])*A[i]; ans+=sum; } cout<<ans.val()<<endl; }