Submission #2214590

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=100000000000000LL;
const int MAX=100001;
const double EPS=1e-10;
int main() {
    int n;
    cin>>n;
    vector<P> v;
    set<int> st;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v.push_back(P(a,i));
    }
    ll ans=0;
    sort(v.begin(),v.end());
    st.insert(-1);st.insert(n);
    for(auto e:v){
        st.insert(e.second);
        auto itr=st.find(e.second);
        ll l,r;
        itr--;
        l=*itr;
        itr++;itr++;
        r=*itr;
        ans+=(ll)(e.second-l)*(ll)(r-e.second)*(ll)e.first;
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result