fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. int countMaxSubarrays(const vector<int>& heights) {
  8.     int n = heights.size();
  9.     vector<int> count(n, 1); // Initializing count for each element as 1
  10.     stack<int> st; // Stack to keep track of indices
  11.  
  12.     // Forward pass to calculate count for each element
  13.     for (int i = 0; i < n; ++i) {
  14.         // Pop elements from the stack while the current height is greater than or equal to the height at the top of the stack
  15.         while (!st.empty() && heights[i] >= heights[st.top()]) {
  16.             count[i] += count[st.top()]; // Add count of popped element to current element's count
  17.             st.pop();
  18.         }
  19.         st.push(i); // Push current index onto the stack
  20.     }
  21.  
  22.     while (!st.empty()) {
  23.         st.pop();
  24.     }
  25.  
  26.     // Backward pass to calculate count for each element
  27.     for (int i = n - 1; i >= 0; --i) {
  28.         // Pop elements from the stack while the current height is greater than the height at the top of the stack
  29.         while (!st.empty() && heights[i] > heights[st.top()]) {
  30.             count[i] += count[st.top()]; // Add count of popped element to current element's count
  31.             st.pop();
  32.         }
  33.         st.push(i); // Push current index onto the stack
  34.     }
  35.  
  36.     int totalCount = 0;
  37.     for (int c : count) {
  38.         totalCount += c; // Sum up the count for each element
  39.     }
  40.  
  41.     return totalCount;
  42. }
  43.  
  44. int main() {
  45.     vector<int> heights = {1,2,1};
  46.     cout << "Count of subarrays with maximum element in each subarray: " << countMaxSubarrays(heights) << endl;
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Count of subarrays with maximum element in each subarray: 5
https://ideone.com/Go93Ic
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!