結果

問題 No.2950 Max Min Product
ユーザー tassei903tassei903
提出日時 2024-10-25 22:23:56
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 535 ms
16,008 KB
testcase_04 AC 588 ms
16,260 KB
testcase_05 AC 552 ms
16,300 KB
testcase_06 AC 776 ms
17,436 KB
testcase_07 AC 774 ms
17,340 KB
testcase_08 AC 776 ms
17,252 KB
testcase_09 AC 374 ms
10,264 KB
testcase_10 AC 672 ms
16,700 KB
testcase_11 AC 585 ms
16,328 KB
testcase_12 AC 777 ms
17,320 KB
testcase_13 AC 778 ms
17,308 KB
testcase_14 AC 779 ms
17,248 KB
testcase_15 AC 826 ms
17,048 KB
testcase_16 AC 622 ms
16,096 KB
testcase_17 AC 684 ms
16,288 KB
testcase_18 AC 870 ms
17,392 KB
testcase_19 AC 877 ms
17,420 KB
testcase_20 AC 877 ms
17,340 KB
testcase_21 AC 512 ms
10,684 KB
testcase_22 AC 686 ms
16,440 KB
testcase_23 AC 449 ms
10,276 KB
testcase_24 AC 902 ms
17,256 KB
testcase_25 AC 905 ms
17,456 KB
testcase_26 AC 909 ms
17,356 KB
testcase_27 AC 836 ms
15,944 KB
testcase_28 AC 1,238 ms
17,032 KB
testcase_29 AC 901 ms
16,216 KB
testcase_30 AC 1,273 ms
17,376 KB
testcase_31 AC 1,175 ms
17,400 KB
testcase_32 AC 1,269 ms
17,320 KB
testcase_33 AC 909 ms
16,188 KB
testcase_34 AC 590 ms
10,164 KB
testcase_35 AC 884 ms
16,144 KB
testcase_36 AC 1,239 ms
17,252 KB
testcase_37 AC 1,234 ms
17,260 KB
testcase_38 AC 1,220 ms
17,300 KB
testcase_39 AC 3 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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