Submission #1589639

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<functional>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<deque>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<bitset>
#include<time.h>
#include<cstdlib>
#include<cassert>
#define ll long long
#define fi first
#define se second
using namespace std;
void aho(string s,ll a){
  cout<<s<<"="<<a<<endl;
  return;
}

int n;
int a[200001];
int b[200001];
                   
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
    b[a[i]]=i+1;
  }
  set<int> s;
  s.insert(0);
  s.insert(n+1);
  ll res=0;
  for(int i=1;i<=n;i++){
    int index=b[i];
    auto ite=s.lower_bound(index);
    ll left=(*ite)-index;
    ite--;
    ll right=index-(*ite);
    res+=i*left*right;
    s.insert(index);
    //aho("left",left);
    //aho("right",right);
    //cout<<res<<endl;
  }
  cout<<res<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Submission Info

Judge Result