fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. template <typename InputIt, typename OutputIt>
  5. void ComputeMinUntilHere(InputIt begin, InputIt end, OutputIt output)
  6. {
  7.     if (begin == end) {
  8.         return;
  9.     }
  10.     auto min = *begin;
  11.     while (begin != end) {
  12.         min = std::min(min, *begin);
  13.         *output = min;
  14.         ++begin;
  15.         ++output;
  16.     }
  17. }
  18.  
  19. struct MinByBlock
  20. {
  21.     std::vector<int> minUntilHere;
  22.     std::vector<int> minStartingHere;
  23. };
  24.  
  25. MinByBlock ComputeMinByBlock(const std::vector<int>&v, std::size_t blockSize)
  26. {
  27.     MinByBlock res;
  28.     res.minUntilHere.resize(v.size());
  29.     res.minStartingHere.resize(v.size());
  30.     for (std::size_t i = 0; i < v.size(); i += blockSize) {
  31.         const auto blockBegin = v.begin() + i;
  32.         const auto blockEndIndex = std::min(i + blockSize, v.size());
  33.         const auto blockEnd = v.begin() + blockEndIndex;
  34.  
  35.         ComputeMinUntilHere(blockBegin, blockEnd, res.minUntilHere.begin() + i);
  36.         ComputeMinUntilHere(std::make_reverse_iterator(blockEnd),
  37.                             std::make_reverse_iterator(blockBegin),
  38.                             std::make_reverse_iterator(res.minStartingHere.begin() + blockEndIndex));
  39.     }
  40.     return res;
  41. }
  42.  
  43. void print(const std::vector<int>& v)
  44. {
  45.     std::cout << "{ ";
  46.     for (const auto e : v) {
  47.         std::cout << e << " "; 
  48.     }
  49.     std::cout << "}\n";
  50. }
  51.  
  52. int main()
  53. {
  54.     const std::vector<int> v = {2, 1, 3, 6, 5, 4, 42};
  55.  
  56.     const auto res = ComputeMinByBlock(v, 2);
  57.  
  58.     print(res.minUntilHere);
  59.     print(res.minStartingHere);
  60.  
  61. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{ 2 1 3 3 5 4 42 }
{ 1 1 3 6 4 4 42 }
https://ideone.com/r34hkE
language:
C++14 (gcc 8.3)
created:
9 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!