結果

問題 No.2950 Max Min Product
コンテスト
ユーザー Today03
提出日時 2024-10-25 22:39:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,754 bytes
コンパイル時間 3,433 ms
コンパイル使用メモリ 255,868 KB
実行使用メモリ 21,668 KB
最終ジャッジ日時 2024-10-25 22:40:00
合計ジャッジ時間 8,588 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

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

ll op1(ll a, ll b) { return min(a, b); }
ll e1() { return INF; }
ll op2(ll a, ll b) { return max(a, b); }
ll e2() { return 0; }
using RangeMinQuery = atcoder::segtree<ll, op1, e1>;
using RangeMaxQuery = atcoder::segtree<ll, op2, e2>;

template <typename T>
struct SegmentTreeDual {
    using F = function<T(T, T)>;
    SegmentTreeDual() = default;
    SegmentTreeDual(int n, F f, T e) {
        this->n = n;
        this->f = f;
        this->e = e;
        dat = vector<T>(n << 1, e);
    }
    void build(const vector<T> &a) {
        assert((int)a.size() == n);
        for (int i = 0; i < (int)a.size(); i++) dat[i + n] = a[i];
    }
    T operator[](int i) {
        assert(0 <= i && i < n);
        i += n;
        T ret = e;
        while (i) {
            ret = f(ret, dat[i]);
            i >>= 1;
        }
        return ret;
    }
    void apply(int l, int r, T x) {
        assert(0 <= l && l <= r && r <= n);
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) dat[l] = f(dat[l], x), l++;
            if (r & 1) r--, dat[r] = f(dat[r], x);
            l >>= 1;
            r >>= 1;
        }
    }
    int size() { return n; }

private:
    int n;
    vector<T> dat;
    F f;
    T e;
};

template <typename T>
SegmentTreeDual<T> RangeAddQuery(int n) {
    return SegmentTreeDual<ll>(n, [](T a, T b) { return a + b; }, 0);
}
template <typename T>
SegmentTreeDual<pair<T, int>> RangeUpdateQuery(int n) {
    auto f = [](pair<T, int> a, pair<T, int> b) {
        return a.second > b.second ? a : b;
    };
    return SegmentTreeDual<pair<T, int>>(n, f, {0, -1});
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    auto raq = RangeAddQuery<ll>(N);
    auto minseg = RangeMinQuery(A);
    auto maxseg = RangeMaxQuery(A);

    mint ans = 0;
    for (int i = 0; i < N; i++) {
        int lo = i, hi = N;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            if (minseg.prod(i, mid + 1) == A[i] || maxseg.prod(i, mid + 1) == A[i]) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        ll mn = A[i], mx = A[i];
        for (int j = i + 1; j <= lo; j++) {
            mn = min(mn, A[j]);
            mx = max(mx, A[j]);
            ll cnt = raq[j];
            ans += mn * mx * (1 + cnt);
            if (cnt > 0) raq.apply(j, j + 1, -1);
        }
        raq.apply(lo + 1, N, 1);
    }
    for (int i = 0; i < N; i++) ans += A[i] * A[i];

    cout << ans.val() << endl;
}
0