Submission #4044989

---

Source Code Expand

#include<bits/stdc++.h>

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  vector<pair<ll,ll>>num(n);
  for(int i=0;i<n;i++){cin>>num[i].F;num[i].S=i+1;}
  sort(ALL(num));
  set<ll>se;
  ll ans=0;
  se.insert(0);se.insert(n+1);
  for(int i=0;i<n;i++){
    auto lb = se.lower_bound(num[i].S);
    ll rnum=*lb-num[i].S-1;
    // cout<<*lb<<" ";
    ll lnum=num[i].S-*(--lb)-1;
    //cout<<*lb<<" "<<i+1<<" "<<rnum<<" "<<lnum<<endl;
    se.insert(num[i].S);
    ans+=(rnum+lnum+rnum*lnum+1)*num[i].F;
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result