結果

問題 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 #
raw source code 

#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;
}
0