Submission #1258756

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int DIM = 2e5 + 5;

vector<int> stk;
int arr[DIM], lef[DIM], rig[DIM];

int main( void ) {
    
    int n;
    cin >> n;
    
    for( int i = 1; i <= n; i ++ )
        cin >> arr[i];
    
    stk.assign( 1, 0 );
    for( int i = 1; i <= n; i ++ ) {
        while( arr[i] <= arr[stk.back()] )
            stk.pop_back();
        
        lef[i] = stk.back() + 1;
        stk.push_back( i );
    }
    
    stk.assign( 1, n + 1 );
    for( int i = n; i >= 1; i -- ) {
        while( arr[i] <= arr[stk.back()] )
            stk.pop_back();
        
        rig[i] = stk.back() - 1;
        stk.push_back( i );
    }
    
    long long ans = 0;
    for( int i = 1; i <= n; i ++ )
        ans += 1LL * arr[i] * ( i - lef[i] + 1 ) * ( rig[i] - i + 1 );
    
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result