Submission #1358492

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
typedef pair<int,int> ii;


int main()
{
    int n;
    cin>>n;

    stack<ii> pile;

    ll t[n];
    ll minLeft[n];
    ll minRight[n];

    for(int i=0;i<n;i++)
    {
        cin>>t[i];
        minRight[i]=i;

        while(!pile.empty() && pile.top().ff>=t[i])
        {
            minRight[pile.top().ss]=i;
            pile.pop();
        }

        if(pile.empty())
            minLeft[i]=-1;
        else
            minLeft[i]=pile.top().ss;
        pile.push(ii(t[i],i));
    }

    while(!pile.empty())
    {
        minRight[pile.top().ss]=n;
        pile.pop();
    }
    ll answer=0;

    for(int i=0;i<n;i++)
    {
        ll nb= (minRight[i]-i)*(i-minLeft[i]);
        answer+=nb*t[i];
    }

    cout<<answer;

}

Submission Info

Judge Result