fork download
copy 
  1. #include <cassert>
  2. #include <map>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. using Hystogram = vector<int>;
  7. using Value = int;
  8. using Column = int;
  9.  
  10. int trap_rain_water(const Hystogram &h) {
  11.   int sum = 0;
  12.  
  13.   map<Value, Column> last_seen_level_at;
  14.   int last_i = 0;
  15.   for (Column col = 0; col < h.size(); ++col) {
  16.     Value i = h[col];
  17.  
  18.     if (i > last_i) {
  19.       // flush prev levels below
  20.       for (auto k = i; k > last_i; --k) {
  21.         if (last_seen_level_at[k] > 0) {
  22.           // how much level taken by water
  23.           sum += (col - last_seen_level_at[k]);
  24.         }
  25.       }
  26.     }
  27.  
  28.     if (i < last_i) {
  29.       // track start col of levels
  30.       for (auto k = last_i; k > i; --k) {
  31.         last_seen_level_at[k] = col;
  32.       }
  33.     }
  34.  
  35.     last_i = i;
  36.   }
  37.   return sum;
  38. }
  39.  
  40. int main() {
  41.   // https://w...content-available-to-author-only...e.com/watch?v=HmBbcDiJapY&t=333s
  42.   Hystogram h = {1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  43.   int result = 1 + 1 + 2 + 1 + 1;
  44.  
  45.   assert(trap_rain_water(h) == result);
  46.   return 0;
  47. }
  48.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j3SXcm
language:
C++14 (gcc 8.3)
created:
6 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!