fork(2) download 
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. #include <utility>
  5.  
  6. std::vector<int> leq_subarrays(const std::vector<int>& numbers) {
  7.   if (numbers.empty()) {
  8.     return std::vector<int>();
  9.   }
  10.   std::vector<int> answer(numbers.size());
  11.   std::stack<std::pair<int, int>> s;
  12.   s.push(std::make_pair(numbers[0], 1));
  13.   answer[0] = 1;
  14.   for (size_t i = 1; i < numbers.size(); ++i) {
  15.     const auto& value = numbers[i];
  16.     int count = 1;
  17.     while (!s.empty() && s.top().first <= value) {
  18.       count += s.top().second;
  19.       s.pop();
  20.     }
  21.     s.push(std::make_pair(value, count));
  22.     answer[i] = count;
  23.   }
  24.   return answer;
  25. }
  26.  
  27. int main() {
  28.   std::vector<int> v = { 1,3,4,2, 5 };
  29.   auto r = leq_subarrays(v);
  30.   for (auto value : r) {
  31.     std::cout << value << ' ';
  32.   }
  33. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 3 1 5
https://ideone.com/SlZorX
language:
C++14 (gcc 8.3)
created:
8 years 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!