Submission #905107

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef vector<int> vi;

#define mp make_pair
#define pb push_back

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
 
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
 
const int MOD = 1000000007;
double PI = 4*atan(1);

int n, t[400000];

void build() {  // build the tree
  for (int i = n - 1; i > 0; --i) t[i] = min(t[i<<1],t[i<<1|1]);
}

int query(int l, int r) {
  int res = n+1;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res,t[l++]);
    if (r&1) res = min(res,t[--r]);
  }
  return res;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	ll x = 0;
	F0R(i,n) cin >> t[n+i];
	build();
	F0R(i,n) {
	    int l = 0, r = i;
	    while (l != r) {
	        if (query((l+r-1)/2,i+1) == t[n+i]) r = (l+r-1)/2;
            else l = (l+r-1)/2+1;
	    }
	    ll ans = i-l+1;
	    l = i, r = n-1;
	    while (l != r) {
	        if (query(i,(l+r+1)/2+1) == t[n+i]) l = (l+r+1)/2;
            else r = (l+r+1)/2-1;
	    }
	    ans *= (r-i+1);
	    x += ans*t[n+i];
	}
	cout << x;
}

Submission Info

Judge Result