結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 3 ms
7,524 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

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