Advertisement
peltorator

Sum of minimums on all subsegments of an array

Jan 4th, 2023 (edited)
1,876
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     int n;
  7.     cin >> n;
  8.     vector<int> arr(n);
  9.     for (int& elem : arr) {
  10.         cin >> elem;
  11.     }
  12.  
  13.     vector<int> l(n);
  14.     vector<int> stack_of_min;
  15.     stack_of_min.push_back(-1);
  16.     for (int i = 0; i < n; i++) {
  17.         while (stack_of_min.back() != -1 && arr[stack_of_min.back()] >= arr[i]) {
  18.             stack_of_min.pop_back();
  19.         }
  20.         l[i] = stack_of_min.back();
  21.         stack_of_min.push_back(i);
  22.     }
  23.  
  24.     vector<int> r(n);
  25.     stack_of_min.clear();
  26.     stack_of_min.push_back(n);
  27.     for (int i = n - 1; i >= 0; i--) {
  28.         while (stack_of_min.back() != -1 && arr[stack_of_min.back()] > arr[i]) {
  29.             stack_of_min.pop_back();
  30.         }
  31.         r[i] = stack_of_min.back();
  32.         stack_of_min.push_back(i);
  33.     }
  34.  
  35.     long long ans = 0;
  36.     for (int i = 0; i < n; i++) {
  37.         ans += 1LL * (i - l[i]) * (r[i] - i) * arr[i];
  38.     }
  39.     cout << ans << endl;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement