fork(6) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. struct Line {
  7.     mutable ll m, b, p;
  8.     bool operator<(const Line &o) const { return m < o.m; }
  9.     bool operator<(const ll &x) const { return p < x; }
  10. };
  11.  
  12. struct LineContainer : multiset<Line, less<>> { // upper convex hull.
  13.     // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  14.     const ll inf = LLONG_MAX;
  15.     ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
  16.     bool isect(iterator x, iterator y) {
  17.         if (y == end()) {
  18.             x->p = inf;
  19.             return false;
  20.         }
  21.         if (x->m == y->m)
  22.             x->p = x->b > y->b ? inf : -inf;
  23.         else
  24.             x->p = div(y->b - x->b, x->m - y->m);
  25.         return x->p >= y->p;
  26.     }
  27.     void add(ll m, ll b) {
  28.         auto z = insert({m, b, 0}), y = z++, x = y;
  29.         while (isect(y, z))
  30.             z = erase(z);
  31.         if (x != begin() && isect(--x, y))
  32.             isect(x, y = erase(y));
  33.         while ((y = x) != begin() && (--x)->p >= y->p)
  34.             isect(x, erase(y));
  35.     }
  36.     ll query(ll x) {
  37.         assert(!empty());
  38.         auto l = *lower_bound(x);
  39.         return l.m * x + l.b;
  40.     }
  41. };
  42.  
  43. const ll is_query = -(1LL << 60);
  44. struct Line2 {
  45.     ll m, b;
  46.     mutable function<const Line2 *()> succ;
  47.     bool operator<(const Line2 &rhs) const {
  48.         if (rhs.b != is_query)
  49.             return m < rhs.m;
  50.         const Line2 *s = succ();
  51.         if (!s)
  52.             return 0;
  53.         ll x = rhs.m;
  54.         return b - s->b < (s->m - m) * x;
  55.     }
  56. };
  57. struct HullDynamic : public multiset<Line2> { // will maintain upper hull for maximum
  58.     bool bad(iterator y) {
  59.         auto z = next(y);
  60.         if (y == begin()) {
  61.             if (z == end())
  62.                 return 0;
  63.             return y->m == z->m && y->b <= z->b;
  64.         }
  65.         auto x = prev(y);
  66.         if (z == end())
  67.             return y->m == x->m && y->b <= x->b;
  68.         return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
  69.     }
  70.     void insert_line(ll m, ll b) {
  71.         auto y = insert({m, b});
  72.         y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
  73.         if (bad(y)) {
  74.             erase(y);
  75.             return;
  76.         }
  77.         while (next(y) != end() && bad(next(y)))
  78.             erase(next(y));
  79.         while (y != begin() && bad(prev(y)))
  80.             erase(prev(y));
  81.     }
  82.     ll eval(ll x) {
  83.         auto l = *lower_bound({x, is_query});
  84.         return l.m * x + l.b;
  85.     }
  86. };
  87. typedef long double ld;
  88. const ld inf = 1e18;
  89.  
  90. struct chtDynamic {
  91.     struct line {
  92.         ll m, b;
  93.         ld x;
  94.         ll val;
  95.         bool isQuery;
  96.         line(ll _m = 0, ll _b = 0) : m(_m), b(_b), val(0), x(-inf), isQuery(false) {}
  97.  
  98.         ll eval(ll x) const { return m * x + b; }
  99.         bool parallel(const line &l) const { return m == l.m; }
  100.         ld intersect(const line &l) const { return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m); }
  101.         bool operator<(const line &l) const {
  102.             if (l.isQuery)
  103.                 return x < l.val;
  104.             else
  105.                 return m < l.m;
  106.         }
  107.     };
  108.  
  109.     set<line> hull;
  110.     typedef set<line>::iterator iter;
  111.  
  112.     bool cPrev(iter it) { return it != hull.begin(); }
  113.     bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }
  114.  
  115.     bool bad(const line &l1, const line &l2, const line &l3) { return l1.intersect(l3) <= l1.intersect(l2); }
  116.     bool bad(iter it) { return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it)); }
  117.  
  118.     iter update(iter it) {
  119.         if (!cPrev(it))
  120.             return it;
  121.         ld x = it->intersect(*prev(it));
  122.         line tmp(*it);
  123.         tmp.x = x;
  124.         it = hull.erase(it);
  125.         return hull.insert(it, tmp);
  126.     }
  127.  
  128.     void addLine(ll m, ll b) {
  129.         line l(m, b);
  130.         iter it = hull.lower_bound(l);
  131.         if (it != hull.end() && l.parallel(*it)) {
  132.             if (it->b < b)
  133.                 it = hull.erase(it);
  134.             else
  135.                 return;
  136.         }
  137.  
  138.         it = hull.insert(it, l);
  139.         if (bad(it))
  140.             return (void)hull.erase(it);
  141.  
  142.         while (cPrev(it) && bad(prev(it)))
  143.             hull.erase(prev(it));
  144.         while (cNext(it) && bad(next(it)))
  145.             hull.erase(next(it));
  146.  
  147.         it = update(it);
  148.         if (cPrev(it))
  149.             update(prev(it));
  150.         if (cNext(it))
  151.             update(next(it));
  152.     }
  153.  
  154.     ll query(ll x) const {
  155.         if (hull.empty())
  156.             return -inf;
  157.         line q;
  158.         q.val = x, q.isQuery = 1;
  159.         iter it = --hull.lower_bound(q);
  160.         return it->eval(x);
  161.     }
  162. } ds;
  163. LineContainer cht1;
  164. HullDynamic cht2;
  165. chtDynamic cht3;
  166. const int NUM_INSERTS = 1e7;
  167. const int NUM_QUERIES = 1e7;
  168. vector<int> res1, res2, res3;
  169. signed main() {
  170.     ios::sync_with_stdio(0);
  171.     cin.tie(0);
  172.     vector<array<int, 2>> lines;
  173.     vector<int> queries;
  174.     for (int i = 0; i < NUM_INSERTS; i++)
  175.         lines.push_back({rand(), rand()});
  176.     for (int i = 0; i < NUM_QUERIES; i++)
  177.         queries.push_back(rand());
  178.  
  179.     clock_t begin;
  180.     begin = clock();
  181.     for (auto i : lines)
  182.         cht1.add(i[0], i[1]);
  183.     for (auto i : queries)
  184.         res1.push_back(cht1.query(i));
  185.  
  186.     cout << "LineContainer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  187.     begin = clock();
  188.     for (auto i : lines)
  189.         cht2.insert_line(i[0], i[1]);
  190.     for (auto i : queries)
  191.         res2.push_back(cht2.eval(i));
  192.  
  193.     cout << "HullDynamic:   " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  194.     begin = clock();
  195.     for (auto i : lines)
  196.         cht3.addLine(i[0], i[1]);
  197.     for (auto i : queries)
  198.         res3.push_back(cht3.query(i));
  199.  
  200.     cout << "chtDynamic:    " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  201.  
  202.     // for (int i = 0; i < res1.size(); i++)
  203.     //     assert(res1[i] == res2[i]);
  204. }
Time limit exceeded #stdin #stdout 5s 343040KB
comments (?)
stdin 
Standard input is empty
stdout 
LineContainer: 0.903006
HullDynamic:   1.12495
https://ideone.com/caYDdF
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!