結果

問題 No.2950 Max Min Product
コンテスト
ユーザー pockyny
提出日時 2025-07-12 18:37:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 207 ms / 3,000 ms
コード長 1,833 bytes
コンパイル時間 832 ms
コンパイル使用メモリ 78,816 KB
実行使用メモリ 7,796 KB
最終ジャッジ日時 2025-07-12 18:38:07
合計ジャッジ時間 11,396 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
typedef long long ll;
ll a[200010],inf = 100000000000000;
mint solve(int l,int r){
    if(r - l==1) return a[l]*a[l];
    int i,mid = (l + r)/2;
    mint ans = solve(l,mid) + solve(mid,r);
    vector<ll> mn_v,mx_v;
    for(i=mid;i<r;i++){
        mn_v.push_back(a[i]);
        mx_v.push_back(a[i]);
    }
    for(i=1;i<mn_v.size();i++){
        mn_v[i] = min(mn_v[i],mn_v[i - 1]);
        mx_v[i] = max(mx_v[i],mx_v[i - 1]);
    }
    vector<mint> sum1(mn_v.size() + 1),sum2(mx_v.size() + 1),sum3(mn_v.size() + 1);
    for(i=1;i<=mn_v.size();i++){
        sum1[i] += sum1[i - 1] + mn_v[i - 1];
        sum2[i] += sum2[i - 1] + mx_v[i - 1];
        sum3[i] += sum3[i - 1] + mn_v[i - 1]*mx_v[i - 1];
    }
    ll mn = inf,mx = -inf;
    int l1 = mid,l2 = mid;
    for(i=mid - 1;i>=l;i--){
        mn = min(mn,a[i]);
        mx = max(mx,a[i]);
        while(l1<r && a[l1]>=mn) l1++;
        while(l2<r && a[l2]<=mx) l2++;
        ans += (mint)mn*mx*(min(l1,l2) - mid);
        if(l1<l2){
            ans += (sum1[l2 - mid] - sum1[l1 - mid])*mx;
        }else{
            ans += (sum2[l1 - mid] - sum2[l2 - mid])*mn;
        }
        ans += sum3.back() - sum3[max(l1,l2) - mid];
        // cout << l << " " << r << " " << l1 << " " << l2 << " " << ans.val() << endl;
    }
    // cout << mn << " " << mx << " " << l1 << " " << l2 << endl;
    // for(mint x:sum1) cout << x.val() << " ";
    // cout << "\n";
    // for(mint x:sum2) cout << x.val() << " ";
    // cout << "\n";
    // cout << "[" << l << "," << r << ") := " << ans.val() << "\n";
    return ans;
}

int main(){
    int i,n; cin >> n;
    for(i=0;i<n;i++) cin >> a[i];
    mint ans = solve(0,n);
    cout << ans.val() << "\n";
}
0