From ff3b67478b1f08b0a2b83565de8a454e23441f3a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 15:41:25 +0200 Subject: more testcases --- content/datastructures/monotonicConvexHull.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'content') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 44bff83..119015e 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,27 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue +// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} + ll m, c; + ll operator()(ll x) {return m*x+c;} }; vector ls; -int ptr = 0; +ll ptr = 0; bool bad(Line l1, Line l2, Line l3) { - return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); + return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll b) { // Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { +void add(ll m, ll c) { // Laufzeit O(1) amortisiert + while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } - ls.push_back({m, b}); + ls.push_back({m, c}); ptr = min(ptr, sz(ls) - 1); } ll query(ll x) { // Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); } \ No newline at end of file -- cgit v1.2.3