結果
問題 | No.2950 Max Min Product |
ユーザー |
![]() |
提出日時 | 2024-10-25 21:46:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 966 ms / 3,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 4,864 ms |
コンパイル使用メモリ | 268,164 KB |
最終ジャッジ日時 | 2025-02-24 22:58:45 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#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 1000000000000000000LL vector<int> a; mint ans = 0; void dfs(int l,int r){ if(l==r)return; if(r-l==1){ ans += mint(a[l]).pow(2); return; } int m = (l+r)/2; dfs(l,m); dfs(m+1,r); vector<vector<int>> t; vector<int> ms; { int mini = Inf32,maxi = -Inf32; for(int i=m;i<r;i++){ mini = min(mini,a[i]); maxi = max(maxi,a[i]); t.push_back({mini,maxi,1}); ms.push_back(maxi); } } { int mini = Inf32,maxi = -Inf32; t.push_back({mini,maxi,0}); ms.push_back(maxi); for(int i=m-1;i>=l;i--){ mini = min(mini,a[i]); maxi = max(maxi,a[i]); t.push_back({mini,maxi,0}); ms.push_back(maxi); } } sort(ms.begin(),ms.end()); ms.erase(unique(ms.begin(),ms.end()),ms.end()); sort(t.rbegin(),t.rend()); vector fc(2,fenwick_tree<mint>(ms.size())); auto fs = fc; rep(i,t.size()){ int pos = lower_bound(ms.begin(),ms.end(),t[i][1])-ms.begin(); mint tt = fs[t[i][2]^1].sum(pos,ms.size()); tt += fc[t[i][2]^1].sum(0,pos)*t[i][1]; tt *= t[i][0]; ans += tt; fc[t[i][2]].add(pos,1); fs[t[i][2]].add(pos,t[i][1]); } } int main(){ int n; cin>>n; a.resize(n); rep(i,n) cin>>a[i]; dfs(0,n); cout<<ans.val()<<endl; return 0; }