Submission #1697893

---

Source Code Expand

#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;
const int INF = 1 << 25;
const LL MOD = 1000000007LL;
using namespace std;
typedef pair<int, int> P;
int a[200000];
int l[200000];
int r[200000];
int main() {
	stack<P> S1, S2;
	int N;
	cin >> N;
	rep(i, N) cin >> a[i];
	S1.push(P(-1, -1));
	for (int i = 0; i < N; i++) {
		while (S1.top().first > a[i]) {
			S1.pop();
		}
		l[i] = i - S1.top().second;
		S1.push(P(a[i], i));
	}
	S2.push(P(-1, N));
	for (int i = N - 1; i >= 0; i--) {
		while (S2.top().first > a[i]) {
			S2.pop();
		}
		r[i] = S2.top().second - i;
		S2.push(P(a[i], i));
	}
	LL sum = 0;
	rep(i, N) {
		sum += (LL)a[i] * l[i] * r[i];
	}
	cout << sum << endl;
}

Submission Info

Judge Result