Submission #1511139

---

Source Code Expand

#include <bits/stdc++.h> 
 
using namespace std;
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 

const int MAX_N=2e5+1;

int main(){
    LL N;cin>>N;
    vector<LL>a(N),b(N+1);
    REP(i,N){
        cin>>a[i];
        b[a[i]]=i;
    }
    set<LL>st;
    LL res=0;
    REP(i,N){
        st.insert(b[i+1]);
        auto itr=st.find(b[i+1]);
        LL l=-1,r=-1;
        auto itr2=itr;
        if(itr!=st.begin()){
            itr2--;l=*itr2;
        }else{
            l=-1;
        }
        itr2=itr;
        itr2++;
        if(itr2!=st.end()){
            r=*itr2;
        }else{
            r=N;
        }
        //cout<<i+1<<":"<<l<<" "<<*itr<<" "<<r<<endl;
        LL tmp=(*itr-l)*(r-*itr)*(i+1LL);
        //cout<<tmp<<endl;
        res+=tmp;
    }
    cout<<res<<endl;
    return 0;
}
//各要素が最小値になりうるのは何回か？
//i番目より前でa[i]より小さい数はどこにあるか？
//i番目より後でa[i]より小さい数はどこにあるか？

Submission Info

Judge Result