fork(3) 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
stdin
Standard input is empty
stdout
LineContainer: 0.903006
HullDynamic:   1.12495