POJ 3658 - Artificial Lake

http://poj.org/problem?id=3658

概要

無限に高い壁で区切られた区間があり、ここを \(N\) 個の部分区間に分ける。 各部分区間の幅は \(W_i\) で高度は \(H_i\) である。

最も高度が低い部分区間の上空から単位時間に単位面積分の水を入れる。 各部分区間が、その高度より1高い位置まで水が張るのにかかる時間を答える。

制約

解法

水を入れている場所のインデックスを I とする。 半開区間 [beg, end) が水に覆われるまでを考えると、[beg, end) の中で最も高い場所のインデックスを lv とすると、 lv < I のときはまず [lv+1, end) の区間が水で覆われ、その後 I の場所から水が溢れながら [beg, I) の区間が水で覆われ、そして最後に I が覆われる。 lv > I のときも同様である。 そんなかんじの再帰で解いた。

区間の中で最も高い場所を求めるのはいわゆる RMQ (Range Minimum Query) 問題なので、SegmentTree で \(O(\log N)\) で求められるようにしておいた。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <functional>
  4 using namespace std;
  5 
  6 const int MAXN = 100000;
  7 long long h[MAXN], w[MAXN];
  8 long long ans[MAXN];
  9 long long wsum[MAXN+1];
 10 int pouring;
 11 
 12 template <class Compare>/*{{{*/
 13 struct SegmentTree
 14 {
 15   const long long *cows;
 16   int *indexes;
 17   int N;
 18   Compare cmp;
 19   SegmentTree(const long long *cs, int n)
 20     : cows(cs), indexes(new int[4*n]), N(n)
 21   {
 22     fill_n(indexes, 4*N, -1);
 23     build(0, 0, N);
 24   }
 25 
 26   void build(int idx, int left, int right)
 27   {
 28     if (left+1 == right) {
 29       indexes[idx] = left;
 30     } else {
 31       const int mid = (left + right)/2;
 32       build(2*idx+1, left, mid);
 33       build(2*idx+2, mid, right);
 34       // minimum in [left, right)
 35       if (cmp(cows[indexes[2*idx+1]], cows[indexes[2*idx+2]])) {
 36         indexes[idx] = indexes[2*idx+1];
 37       } else {
 38         indexes[idx] = indexes[2*idx+2];
 39       }
 40     }
 41   }
 42 
 43   inline long long query_value(int left, int right) const { return cows[query_index(left, right)]; }
 44 
 45   inline int query_index(int left, int right) const { return query_index(left, right, 0, 0, N); }
 46 
 47   int query_index(int left, int right, int i, int a, int b) const
 48   {
 49     // [a, b) is the range of indexes[i]
 50     if (b <= left || right <= a) {
 51       // does not intersect
 52       return -1;
 53     } else if (left <= a && b <= right) {
 54       // contains
 55       return indexes[i];
 56     } else {
 57       const int m = (a+b)/2;
 58       const int l = query_index(left, right, 2*i+1, a, m);
 59       const int r = query_index(left, right, 2*i+2, m, b);
 60       if (l == -1) {
 61         return r;
 62       } else if (r == -1) {
 63         return l;
 64       } else {
 65         if (cmp(cows[l], cows[r])) {
 66           return l;
 67         } else {
 68           return r;
 69         }
 70       }
 71     }
 72   }
 73 };/*}}}*/
 74 
 75 long long t = 0;
 76   template <class T>
 77 void solve(int beg, int end, int prevh, const SegmentTree<T>& segtree)
 78 {
 79   if (beg >= end) {
 80     return;
 81   }
 82   int lv = segtree.query_index(beg, end);
 83   if (lv < pouring) {
 84     solve(lv+1, end, h[lv], segtree);
 85     solve(beg, lv, h[lv], segtree);
 86   } else {
 87     solve(beg, lv, h[lv], segtree);
 88     solve(lv+1, end, h[lv], segtree);
 89   }
 90   ans[lv] = t + (wsum[end] - wsum[beg]);
 91   t += (prevh - h[lv]) * (wsum[end] - wsum[beg]);
 92 }
 93 
 94 int main()
 95 {
 96   int N;
 97   scanf("%d", &N);
 98   long long m = 1LL<<50;
 99   for (int i = 0; i < N; i++) {
100     scanf("%lld %lld", &w[i], &h[i]);
101     wsum[i+1] = wsum[i] + w[i];
102     if (h[i] < m) {
103       m = h[i];
104       pouring = i;
105     }
106   }
107   SegmentTree<greater<long long> > segtree(h, N);
108   int hh = segtree.query_value(0, N);
109   solve(0, N, hh, segtree);
110   for (int i = 0; i < N; i++) {
111     printf("%lld\n", ans[i]);
112   }
113   return 0;
114 }
poj/3658.cc