結果

問題 No.2950 Max Min Product
コンテスト
ユーザー tassei903
提出日時 2024-10-25 22:23:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,273 ms / 3,000 ms
コード長 2,793 bytes
コンパイル時間 4,514 ms
コンパイル使用メモリ 294,732 KB
実行使用メモリ 17,456 KB
最終ジャッジ日時 2024-10-25 23:31:09
合計ジャッジ時間 36,113 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define all(x) begin(x), end(x)


typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;


template<typename T>
ostream &operator<< (ostream& os, const vector<T> &v){
	rep(i, 0, sz(v)) {
		os << v[i];
		if (i < sz(v)-1)os << " ";
	}
	return os;
}

template<typename S, typename T>
ostream &operator<< (ostream& os, const pair<S, T> &p){
	os << "(" << p.first << ", " << p.second << ") ";
    return os;
}

void out(){
	cout << endl;
}
template<class T> void out(vector<T> x) { for (int i = 0; i < sz(x); i++) cout << x[i] << " \n"[i == sz(x) - 1]; }
template<class S, class T> void out(pair<S, T> x){ cout  << "(" << x.first << ", " << x.second << ") ";}
template<class T> void out(set<T> x) {
    for (auto y: x) cout << y << " ";
    cout << endl;
}

template<typename Head, typename ...Tail>
void out(Head h, Tail ...t) {
	cout << h << " ";
	out(t...);
}

template<class T>
void chmin(T &a, const T x) {
    a = min(a, x);
}

using pii = pair<int, int>;

#include<atcoder/lazysegtree>
#include<atcoder/modint>
using mint = atcoder::modint998244353;

void solve() {
    int n;cin >> n;
    vector<int> a(n);rep(i, 0, n) cin >> a[i];

    struct S{
        mint AB, A, B, cnt;
    };

    auto op = [&](S x, S y)->S {
        return {x.AB + y.AB, x.A + y.A, x.B + y.B, x.cnt + y.cnt};
    };
    
    auto e = [&] {
        return S{0, 0, 0, 0};
    };

    struct F {
        mint x, y;
    };

    auto mapping = [&](F f, S x)->S {
        return {x.AB + f.y * x.A + f.x * x.B + f.x * f.y * x.cnt, x.A + f.x * x.cnt, x.B + f.y * x.cnt, x.cnt};
    };

    auto composition = [&](F f, F g) -> F {
        return {f.x + g.x, f.y + g.y};
    };

    auto id = [&]->F {
        return {0, 0};
    };

    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S>(n, {0,0,0,1}));

    stack<int> stmin, stmax;stmin.push(-1);stmax.push(-1);
    mint ans = 0;
    rep(i, 0, n) {
        while (stmin.top() != -1 && a[stmin.top()] >= a[i]) {
            int r = stmin.top();stmin.pop();
            int l = stmin.top();
            seg.apply(l+1, r+1, {-a[r], 0});
        }
        int l = stmin.top();
        seg.apply(l+1, i+1, {a[i], 0});
        stmin.push(i);

        while (stmax.top() != -1 && a[stmax.top()] <= a[i]) {
            int r = stmax.top();stmax.pop();
            int l = stmax.top();
            seg.apply(l+1, r+1, {0, -a[r]});
        }
        l = stmax.top();
        seg.apply(l+1, i+1, {0, a[i]});
        stmax.push(i);


        ans += seg.prod(0, i+1).AB;
    }
    cout << ans.val() << endl;

}


int main() {
    std::cin.tie(0)->sync_with_stdio(0);

    int T = 1;
    while (T--)solve();
}
0