Fixing two errors in convex hull optimization code.

3 files changed, 6 insertions, 4 deletions

diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
index 9ccf220..042d26c 100644
--- a/datastructures/dynamicConvexHull.cpp
+++ b/datastructures/dynamicConvexHull.cpp
@@ -3,7 +3,7 @@ struct Line {
     ll m, b;
     mutable function<const Line*()> succ;
     bool operator<(const Line& rhs) const {
-        if (rhs.b != is_query) return m < rhs.m;
+        if (rhs.b != LLONG_MIN) return m < rhs.m;
         const Line* s = succ();
         if (!s) return 0;
         ll x = rhs.m;
@@ -28,8 +28,8 @@ struct HullDynamic : public multiset<Line> {
         while (next(y) != end() && bad(next(y))) erase(next(y));
         while (y != begin() && bad(prev(y))) erase(prev(y));
     }
-    ll query(ll x) { // Laufzeit: O(log(n))
-        auto l = *lower_bound((Line) { x, -(1LL<<62) });
+    ll query(ll x) { // Laufzeit: O(log(n)) 
+        auto l = *lower_bound((Line) {x, LLONG_MIN});
         return l.m * x + l.b;
     }
 };
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
index a93bfae..64af841 100644
--- a/datastructures/monotonicConvexHull.cpp
+++ b/datastructures/monotonicConvexHull.cpp
@@ -10,7 +10,9 @@ void add(ll m, ll b) { // Laufzeit O(1) amortisiert
   ms.push_back(m); bs.push_back(b);
   while (ms.size() >= 3 && bad(ms.size() - 3, ms.size() - 2, ms.size() - 1)) {
     ms.erase(ms.end() - 2); bs.erase(bs.end() - 2);
-}}
+  }
+  ptr = min(ptr, ms.size() - 1);
+}
 
 ll get(int idx, ll x) { return ms[idx] * x + bs[idx]; }
 
diff --git a/tcr.pdf b/tcr.pdf
index f55eaaa..0d9ec62 100644
--- a/tcr.pdf
+++ b/tcr.pdf