diff options
| -rw-r--r-- | datastructures/datastructures.tex | 8 | ||||
| -rw-r--r-- | datastructures/treap2.cpp | 3 | ||||
| -rw-r--r-- | geometry/closestPair.cpp | 6 | ||||
| -rw-r--r-- | other/knuth.cpp | 2 | ||||
| -rw-r--r-- | tcr.pdf | bin | 647782 -> 647987 bytes |
5 files changed, 11 insertions, 8 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index fc72b0b..85ad693 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -89,6 +89,10 @@ \sourcecode{datastructures/stlTree.cpp} \end{algorithm} +\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} + \sourcecode{datastructures/stlRope.cpp} +\end{algorithm} + \begin{algorithm}{STL HashMap} 3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map} \sourcecode{datastructures/stlHashMap.cpp} @@ -99,10 +103,6 @@ \sourcecode{datastructures/stlPQ.cpp} \end{algorithm} -\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} - \sourcecode{datastructures/stlRope.cpp} -\end{algorithm} - \begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. \sourcecode{datastructures/monotonicConvexHull.cpp} diff --git a/datastructures/treap2.cpp b/datastructures/treap2.cpp index 5d0aefa..10168ca 100644 --- a/datastructures/treap2.cpp +++ b/datastructures/treap2.cpp @@ -41,7 +41,8 @@ struct Treap { upd(v); return {left, v}; } else { - auto [left, right] = split(V->r, k - getSize(V->l) - 1); // and only "k" + // and only "k" + auto [left, right] = split(V->r, k - getSize(V->l) - 1); V->r = left; upd(v); return {v, right}; diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp index 7acdeca..6cde5ae 100644 --- a/geometry/closestPair.cpp +++ b/geometry/closestPair.cpp @@ -21,8 +21,10 @@ double shortestDist(vector<pt>& pts) { // sz(pts) > 1 status.erase(*left); left++; } else { - auto lower = status.lower_bound({-1.0/0.0, imag(*right) - sqrtOpt}); - auto upper = status.upper_bound({-1.0/0.0, imag(*right) + sqrtOpt}); + auto lower = status.lower_bound({-1.0/0.0, //-INF + imag(*right) - sqrtOpt}); + auto upper = status.upper_bound({-1.0/0.0, //-INF + imag(*right) + sqrtOpt}); for (;lower != upper; lower++) { double cand = norm(*right - *lower); if (cand < opt) { diff --git a/other/knuth.cpp b/other/knuth.cpp index f47dbe0..f619f82 100644 --- a/other/knuth.cpp +++ b/other/knuth.cpp @@ -6,7 +6,7 @@ ll calc(int n, int k, const vector<vector<ll>> &C) { for (int i = 1; i < k; i++) { for (int j = n - 1; j >= 0; --j) { opt[i][j] = i == 1 ? 0 : opt[i - 1][j]; - for (int k = opt[i][j]; k <= min(opt[i][j + 1], j - 1); ++k) { + for (int k = opt[i][j]; k <= min(opt[i][j+1], j-1); k++) { if (dp[i][j] <= dp[i - 1][k] + C[k + 1][j]) continue; dp[i][j] = dp[i - 1][k] + C[k + 1][j]; opt[i][j] = k; Binary files differ |