結果
問題 | No.2950 Max Min Product |
ユーザー |
|
提出日時 | 2024-10-25 21:45:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 386 ms / 3,000 ms |
コード長 | 1,523 bytes |
コンパイル時間 | 1,211 ms |
コンパイル使用メモリ | 91,264 KB |
実行使用メモリ | 18,492 KB |
最終ジャッジ日時 | 2024-10-25 23:30:00 |
合計ジャッジ時間 | 13,928 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include<iostream> #include<vector> #include<cassert> #include<atcoder/modint> #include<atcoder/lazysegtree> using namespace std; using mint=atcoder::modint998244353; using dat=pair<mint,int>; dat op(dat a,dat b) { a.first+=b.first; a.second+=b.second; return a; } dat e(){return make_pair(mint::raw(0),0);} dat mp(int f,dat x) { if(f>=0)x.first=x.second*mint(f); return x; } int cmp(int f,int g){return f>=0?f:g;} int id(){return -1;} int N; int A[2<<17]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N; for(int i=0;i<N;i++)cin>>A[i]; mint ans=0,ret=0; atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>segmax(N),segmin(N); vector<pair<int,int> >mx,mn; mx.push_back(make_pair(N,(int)1e9)); mn.push_back(make_pair(N,0)); for(int i=N;i--;) { segmax.set(i,make_pair(A[i],1)); segmin.set(i,make_pair(A[i],1)); {//max while(mx.back().second<A[i]) { int l=mx.back().first; int a=mx.back().second; mx.pop_back(); ans-=segmin.prod(l,mx.back().first).first*a; } segmax.apply(i,mx.back().first,A[i]); ans+=segmin.prod(i+1,mx.back().first).first*A[i]; mx.push_back(make_pair(i,A[i])); } {//min while(mn.back().second>A[i]) { int l=mn.back().first; int a=mn.back().second; mn.pop_back(); ans-=segmax.prod(l,mn.back().first).first*a; } segmin.apply(i,mn.back().first,A[i]); ans+=segmax.prod(i+1,mn.back().first).first*A[i]; mn.push_back(make_pair(i,A[i])); } ans+=mint(A[i])*A[i]; ret+=ans; } cout<<ret.val()<<"\n"; }