結果

問題 No.2950 Max Min Product
ユーザー V_Melville
提出日時 2024-10-25 22:31:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,652 bytes
コンパイル時間 3,111 ms
コンパイル使用メモリ 251,312 KB
実行使用メモリ 29,180 KB
最終ジャッジ日時 2024-10-25 22:31:26
合計ジャッジ時間 15,904 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9;
int n, a[500005], ans = 0;
struct node {
    int l, r, sa1, sb1, sa2, sb2, ans1, ans2;
} tr[2000005];
struct tag {
    int a1, a2;
} lazy[2000005];
#define ls (p * 2)
#define rs (p * 2 + 1)
void pushup(int p) {
    tr[p].sa1 = (tr[ls].sa1 + tr[rs].sa1) % mod;
    tr[p].sb1 = (tr[ls].sb1 + tr[rs].sb1) % mod;
    tr[p].sa2 = (tr[ls].sa2 + tr[rs].sa2) % mod;
    tr[p].sb2 = (tr[ls].sb2 + tr[rs].sb2) % mod;
    tr[p].ans1 = (tr[ls].ans1 + tr[rs].ans1) % mod;
    tr[p].ans2 = (tr[ls].ans2 + tr[rs].ans2) % mod; 
}
void build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;
    tr[p].sa1 = tr[p].sb1 = tr[p].sa2 = tr[p].sb2 = 0;
    tr[p].ans1 = tr[p].ans2 = 0;
    if (l == r) return ;
    int mid = (l + r) / 2;
    build(ls, l, mid), build(rs, mid + 1, r);
}
void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
void add_tag(int p, tag t) {
    if (t.a1) {
        add(lazy[p].a1, t.a1);
        add(tr[p].ans1, 1ll * tr[p].sb1 * t.a1 % mod);
        add(tr[p].ans2, 1ll * tr[p].sb2 * t.a1 % mod);
        add(tr[p].sa1, 1ll * (tr[p].r - tr[p].l + 1) * t.a1 % mod);
        add(tr[p].sa2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a1 % mod);
    }
    if (t.a2) {
        add(lazy[p].a2, t.a2);
        add(tr[p].ans1, 1ll * tr[p].sa1 * t.a2 % mod);
        add(tr[p].ans2, 1ll * tr[p].sa2 * t.a2 % mod);
        add(tr[p].sb1, 1ll * (tr[p].r - tr[p].l + 1) * t.a2 % mod);
        add(tr[p].sb2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a2 % mod);
    }
}
void pushdown(int p) {
    if (lazy[p].a1 or lazy[p].a2) {
        add_tag(ls, lazy[p]);
        add_tag(rs, lazy[p]);
        lazy[p] = (tag){0, 0};
    }
}
void update(int p, int x, int y, tag t) {
    if (tr[p].l >= x && tr[p].r <= y) {
        return add_tag(p, t), void();
    }
    pushdown(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    if (x <= mid) update(ls, x, y, t);
    if (mid < y) update(rs, x, y, t);
    pushup(p);
}
#undef ls
#undef rs
int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    stack <int> sta1, sta2;
    sta1.push(0), sta2.push(0);
    for (int i = 1; i <= n; ++i) {
        while (sta1.top() && a[ sta1.top() ] <= a[i]) {
            int x = sta1.top(), val = a[ sta1.top() ]; sta1.pop();
            update(1, sta1.top() + 1, x, (tag){a[i] - val, 0});
        }
        sta1.push(i), update(1, i, i, (tag){a[i], 0});
        while (sta2.top() && a[ sta2.top() ] >= a[i]) {
            int x = sta2.top(), val = a[ sta2.top() ]; sta2.pop();
            update(1, sta2.top() + 1, x, (tag){0, a[i] - val + mod});
        }
        sta2.push(i), update(1, i, i, (tag){0, a[i]});
        (ans += (1ll * tr[1].ans1 * (i + 1) % mod - tr[1].ans2 + mod) % mod) %= mod;
    }
    cout << ans << '\n';
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0