From 025b4a5abd77a705c313aee0b8d329fed4f47c42 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Wed, 3 Jan 2018 17:06:36 +0100 Subject: Fixing two errors in convex hull optimization code. --- datastructures/monotonicConvexHull.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'datastructures/monotonicConvexHull.cpp') 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]; } -- cgit v1.2.3