結果

問題 No.2950 Max Min Product
ユーザー zawakasuzawakasu
提出日時 2024-10-28 13:15:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,802 ms / 3,000 ms
コード長 5,698 bytes
コンパイル時間 1,533 ms
コンパイル使用メモリ 92,276 KB
実行使用メモリ 31,076 KB
最終ジャッジ日時 2024-10-28 13:16:37
合計ジャッジ時間 59,594 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1,296 ms
22,048 KB
testcase_04 AC 1,345 ms
23,964 KB
testcase_05 AC 1,342 ms
22,764 KB
testcase_06 AC 1,692 ms
30,644 KB
testcase_07 AC 1,704 ms
30,640 KB
testcase_08 AC 1,693 ms
30,700 KB
testcase_09 AC 927 ms
17,244 KB
testcase_10 AC 1,632 ms
27,104 KB
testcase_11 AC 1,351 ms
23,896 KB
testcase_12 AC 1,690 ms
30,676 KB
testcase_13 AC 1,714 ms
30,752 KB
testcase_14 AC 1,685 ms
30,664 KB
testcase_15 AC 1,802 ms
28,916 KB
testcase_16 AC 1,233 ms
21,852 KB
testcase_17 AC 1,392 ms
23,712 KB
testcase_18 AC 1,703 ms
30,640 KB
testcase_19 AC 1,680 ms
30,688 KB
testcase_20 AC 1,676 ms
30,600 KB
testcase_21 AC 1,082 ms
19,780 KB
testcase_22 AC 1,280 ms
24,248 KB
testcase_23 AC 906 ms
17,728 KB
testcase_24 AC 1,695 ms
30,944 KB
testcase_25 AC 1,698 ms
30,948 KB
testcase_26 AC 1,694 ms
31,076 KB
testcase_27 AC 1,221 ms
21,872 KB
testcase_28 AC 1,785 ms
29,308 KB
testcase_29 AC 1,289 ms
22,716 KB
testcase_30 AC 1,791 ms
30,580 KB
testcase_31 AC 1,745 ms
30,696 KB
testcase_32 AC 1,748 ms
30,692 KB
testcase_33 AC 1,326 ms
23,360 KB
testcase_34 AC 841 ms
16,924 KB
testcase_35 AC 1,257 ms
22,800 KB
testcase_36 AC 1,734 ms
30,552 KB
testcase_37 AC 1,713 ms
30,460 KB
testcase_38 AC 1,760 ms
30,576 KB
testcase_39 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <optional>
#include <cassert>
#include <stack>

const long long MOD{998244353};

long long norm(long long v) {
    return ((v % MOD) + MOD) % MOD;
}

long long add(long long L, long long R) {
    return (norm(L) + norm(R)) % MOD;
}

long long mult(long long L, long long R) {
    return (norm(L) * norm(R)) % MOD;
}
struct VD {
    long long max_sum{}, min_sum{}, prod_sum{};
    int len{};
    VD() = default;
    VD(long long mx, long long mn, long long pr, int l)
        : max_sum{mx}, min_sum{mn}, prod_sum{pr}, len{l} {}
};

struct VM {
    using T = VD;
    static T identity() {
        return VD{};
    }
    static T operation(T L, T R) {
        L.max_sum = add(L.max_sum, R.max_sum);
        L.min_sum = add(L.min_sum, R.min_sum);
        L.prod_sum = add(L.prod_sum, R.prod_sum);
        L.len += R.len;
        return L;
    }
};

struct OM {
    using T = std::pair<std::optional<int>, std::optional<int>>;
    static T identity() {
        return T{ std::nullopt, std::nullopt };
    }
    static T operation(T L, T R) {
        if (R.first) L.first = R.first;
        if (R.second) L.second = R.second;
        return L;
    }
};

VM::T mapping(VM::T v, OM::T o) {
    if (o.first and o.second) {
        v.max_sum = mult(*o.first, v.len);
        v.min_sum = mult(*o.second, v.len);
        v.prod_sum = mult(*o.first, mult(*o.second, v.len));
    }
    else if (o.first) {
        v.max_sum = mult(*o.first, v.len);
        v.prod_sum = mult(*o.first, v.min_sum);
    }
    else if (o.second) {
        v.min_sum = mult(*o.second, v.len);
        v.prod_sum = mult(*o.second, v.max_sum);
    }
    return v;
}

struct LazySegmentTree {
    using V = VM::T;
    using O = OM::T;
    static int parent(int v) {
        return v >>= 1;
    }
    static int left(int v) {
        return v << 1;
    }
    static int right(int v) {
        return v << 1 | 1;
    }
    static int depth(int v) {
        return 31 - __builtin_clz(v);
    }
    static int trailingZeros(int v) {
        return __builtin_ctz(v);
    }

    struct Node {
        V v{VM::identity()};
        O o{OM::identity()};
    };

    int n{};
    std::vector<Node> dat;
    static V action(const Node& node) {
        return mapping(node.v, node.o);
    }
    void propagate(int v) {
        dat[left(v)].o = OM::operation(dat[left(v)].o, dat[v].o);
        dat[right(v)].o = OM::operation(dat[right(v)].o, dat[v].o);
        dat[v].o = OM::identity();
    }
    void propagateAncestor(int v) {
        int dep{depth(v)};
        int zeros{trailingZeros(v)};
        for (int d{dep} ; d != zeros ; d--) {
            propagate(v >> d);
        }
    }
    void recalc(int v) {
        dat[v].v = VM::operation(action(dat[left(v)]), action(dat[right(v)]));
    }
    void recalcAncestor(int v) {
        v >>= trailingZeros(v);
        for (v = parent(v) ; v ; v = parent(v)) {
            recalc(v);
        }
    }
    LazySegmentTree() = default;
    LazySegmentTree(const std::vector<V>& A) : n{(int)A.size()}, dat(A.size() << 1) {
        assert(A.size());
        for (int i{} ; i < n ; i++) dat[i + n].v = A[i];
        for (int i{n} ; --i ; ) {
            dat[i].v = VM::operation(dat[left(i)].v, dat[right(i)].v);
        }
    }
    int size() const {
        return n;
    }
    void operation(int L, int R, const O& o) {
        assert(0 <= L and L <= R and R <= n);
        L += size();
        R += size();
        propagateAncestor(L);
        propagateAncestor(R);
        for (int l{L}, r{R} ; l < r ; l = parent(l), r = parent(r)) {
            if (l & 1) {
                dat[l].o = OM::operation(dat[l].o, o);
                l++;
            }
            if (r & 1) {
                r--;
                dat[r].o = OM::operation(dat[r].o, o); 
            }
        }
        recalcAncestor(L);
        recalcAncestor(R);
    }
    V product(int L, int R) {
        assert(0 <= L and L <= R and R <= n);
        L += size();
        R += size();
        propagateAncestor(L);
        propagateAncestor(R);
        recalcAncestor(L);
        recalcAncestor(R);
        V l{VM::identity()}, r{VM::identity()};
        for ( ; L < R ; L = parent(L), R = parent(R)) {
            if (L & 1) {
                l = VM::operation(l, action(dat[L]));
                L++;
            }
            if (R & 1) {
                R--;
                r = VM::operation(action(dat[R]), r);
            }
        }
        return VM::operation(l, r);
    }
};

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

    int N;
    std::cin >> N;
    std::vector<int> A(N);
    std::vector<VM::T> init(N);
    for (int i{} ; i < N ; i++) {
        int a;
        std::cin >> a;
        A[i] = a;
        init[i] = VM::T{a, a, (long long)a * a, 1};
    }
    std::vector<int> prevmax(N, -1), prevmin(N, -1);
    {
        std::stack<int> stack;
        for (int i{} ; i < N ; i++) {
            while (stack.size() and A[stack.top()] < A[i]) stack.pop();
            prevmax[i] = stack.size() ? stack.top() : -1;
            stack.push(i);
        }
    }
    {
        std::stack<int> stack;
        for (int i{} ; i < N ; i++) {
            while (stack.size() and A[stack.top()] > A[i]) stack.pop();
            prevmin[i] = stack.size() ? stack.top() : -1;
            stack.push(i);
        }
    }
    LazySegmentTree seg{init};
    long long ans{};
    for (int i{} ; i < N ; i++) {
        seg.operation(prevmax[i] + 1, i, OM::T{ A[i], std::nullopt }); 
        seg.operation(prevmin[i] + 1, i, OM::T{ std::nullopt, A[i] }); 
        ans = add(ans, seg.product(0, i + 1).prod_sum);
    }
    std::cout << ans << '\n';
}
0