nikunjsoni

907

Apr 7th, 2021
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int sumSubarrayMins(vector<int>& arr) {
  4.         long ans=0, mod=int(1e9)+7, sz=arr.size();
  5.         stack< pair<int, int> > s1, s2;
  6.        
  7.         vector<int> left(sz), right(sz);
  8.         for(int i=0; i<sz; i++){
  9.             int count = 1;
  10.             while(!s1.empty() && s1.top().first >= arr[i]){
  11.                 count += s1.top().second;
  12.                 s1.pop();
  13.             }
  14.             s1.push({arr[i], count});
  15.             left[i] = count;
  16.         }
  17.        
  18.         for(int i=sz-1; i>=0; i--){
  19.             int count = 1;
  20.             while(!s2.empty() && s2.top().first > arr[i]){
  21.                 count += s2.top().second;
  22.                 s2.pop();
  23.             }
  24.             s2.push({arr[i], count});
  25.             right[i] = count;
  26.         }
  27.        
  28.         for(int i=0; i<sz; i++)
  29.             ans = (ans+(long(left[i])*right[i]*arr[i])%mod)%mod;        
  30.         return ans;
  31.     }
  32. };
RAW Paste Data