diff options
Diffstat (limited to 'datastructures/monotonicConvexHull.cpp')
| -rw-r--r-- | datastructures/monotonicConvexHull.cpp | 21 |
1 files changed, 11 insertions, 10 deletions
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 64af841..8035b17 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -3,21 +3,22 @@ vector<ll> ms, bs; int ptr = 0; bool bad(int l1, int l2, int l3) { - return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); + return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < + (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); } 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); + ms.push_back(m); bs.push_back(b); + while (sz(ms) >= 3 && bad(sz(ms)-3, sz(ms)-2, sz(ms)-1)) { + ms.erase(ms.end() - 2); bs.erase(bs.end() - 2); + } + ptr = min(ptr, sz(ms) - 1); } -ll get(int idx, ll x) { return ms[idx] * x + bs[idx]; } +ll get(int idx, ll x) {return ms[idx] * x + bs[idx];} ll query(ll x) { // Laufzeit: O(1) amortisiert - if (ptr >= (int)ms.size()) ptr = ms.size() - 1; - while (ptr < (int)ms.size() - 1 && get(ptr + 1, x) < get(ptr, x)) ptr++; - return ms[ptr] * x + bs[ptr]; + if (ptr >= sz(ms)) ptr = sz(ms) - 1; + while (ptr < sz(ms)-1 && get(ptr + 1, x) < get(ptr, x)) ptr++; + return get(ptr, x); } |