提出 #66127842

---

ソースコード 拡げる

#include <iostream>
#include <stack>
using namespace std;
#define LL long long
#define MaxN 200005
LL n, a[MaxN], l[MaxN], r[MaxN], tr[MaxN];
stack <int> s;

int lowbit(int x) {
	return x & -x;
}
void add(int x, int k) {
	while (x <= n) {
		tr[x] += k;
		x += lowbit(x);
	}
}
LL calc(int x) {
	LL re = 0;
	while (x > 0) {
		re += tr[x];
		x -= lowbit(x);
	}
	return re;
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) {
		while (!s.empty() && a[i] > a[s.top()]) s.pop();
		if (s.empty()) l[i] = i-1;
		else l[i] = i-s.top()-1;
		s.push(i);
	}

	while(!s.empty()) s.pop();
	for(int i = n; i >= 1; i--) {
		while (!s.empty() && a[i] >= a[s.top()]) s.pop();
		if (s.empty()) r[i] = n-i;
		else r[i] = s.top()-i-1;
		s.push(i);
	}


	for(int i = 1; i <= n; i++) {
		int w = min(l[i], r[i]);
		for(int j = 1; j <= w+1; j++) add(j, a[i]);
		for(int j = l[i]+r[i]-w+2; j <= l[i]+r[i]+2; j++) add(j, -a[i]);
	}

	for(int i = 1; i <= n; i++) {
		cout << calc(i) << endl;
	}
	return 0;
}

提出情報

ジャッジ結果