Guest User

Untitled

a guest
Mar 28th, 2017
2,799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const ll is_query = -(1LL << 62);
  2.  
  3. struct Line {
  4.     ll m, b;
  5.     mutable function<const Line *()> succ;
  6.  
  7.     bool operator<(const Line &rhs) const {
  8.         if (rhs.b != is_query) return m < rhs.m;
  9.         const Line *s = succ();
  10.         if (!s) return 0;
  11.         ll x = rhs.m;
  12.         return b - s->b < (s->m - m) * x;
  13.     }
  14. };
  15.  
  16. struct HullDynamic : public multiset<Line> {
  17.     bool bad(iterator y) {
  18.         auto z = next(y);
  19.         if (y == begin()) {
  20.             if (z == end()) return 0;
  21.             return y->m == z->m && y->b <= z->b;
  22.         }
  23.         auto x = prev(y);
  24.         if (z == end()) return y->m == x->m && y->b <= x->b;
  25.         return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
  26.     }
  27.  
  28.     void insert_line(ll m, ll b) {
  29.         auto y = insert({m, b});
  30.         y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
  31.         if (bad(y)) {
  32.             erase(y);
  33.             return;
  34.         }
  35.         while (next(y) != end() && bad(next(y))) erase(next(y));
  36.         while (y != begin() && bad(prev(y))) erase(prev(y));
  37.     }
  38.  
  39.     ll eval(ll x) {
  40.         auto l = *lower_bound((Line) {x, is_query});
  41.         return l.m * x + l.b;
  42.     }
  43. };
RAW Paste Data