Submission #1828637

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int MAXN = 2*1e5 + 10;
int v[MAXN],antes[MAXN],depois[MAXN],n;
long long resposta;
int main(){
	stack<ii> pilha;
	cin.tie(0);ios_base::sync_with_stdio(0);
	cin >> n;
	v[0] = v[n+1] = -1;
	for(int i = 1;i<=n;i++){
		cin >> v[i];
	}
	pilha.push(ii(-1,0));
	for(int i = 1;i<=n+1;i++){
		ii davez = ii(v[i],i);
		while(pilha.top() > davez){
			//printf("Depois de %d eh %d\n",pilha.top().second,i);
			depois[pilha.top().second] = i;
			pilha.pop();
		}
		antes[i] = pilha.top().second;
		pilha.push(davez);
	}
	for(int i = 1;i<=n;i++){
		antes[i]++;
		depois[i]--;
		int esq = abs(i - antes[i]) + 1;
		int dir  = abs(depois[i] - i) + 1;
		resposta += 1LL*esq*dir*v[i];
	}
	cout << resposta << endl;
	return 0;
}

Submission Info

Judge Result