This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
package library.ds; import library.ds.deque.MyDeque; import library.ds.pair.IntPair; /** * Convex Hull Trick Add Monotone * 整数型にしか対応していない * @deprecated verifyしていない * @see <a href="https://ei1333.github.io/library/structure/convex-hull-trick/convex-hull-trick-add-monotone.hpp">参考元</a> */ public final class ConvexHullTrick { private final MyDeque<IntPair> h; private final boolean isMin; public ConvexHullTrick(final boolean isMin) { this.isMin = isMin; h = new MyDeque<>(); } private final boolean isEmpty(){ return h.isEmpty(); } public final void clear(){ h.clear(); } public final int size(){ return h.size(); } public final MyDeque<IntPair> get(){ return h; } private final int sgn(final long x){ return x == 0 ? 0 : (x < 0 ? -1 : 1); } private final boolean check(final IntPair a, final IntPair b, final IntPair c) { if(b.second.longValue() == a.second.longValue() || c.second.longValue() == b.second.longValue()) { return sgn(b.first.longValue() - a.first.longValue()) * sgn(c.second.longValue() - b.second.longValue()) >= sgn(c.first.longValue() - b.first.longValue()) * sgn(b.second.longValue() - a.second.longValue()); } return (b.second.longValue() - a.second.longValue()) / (a.first.longValue() - b.first.longValue()) >= (c.second.longValue() - b.second.longValue()) / (b.first.longValue() - c.first.longValue()); } public final void add(long a, long b) { if(!isMin) { a = -a; b = -b; } final IntPair line = IntPair.of(a, b); if(isEmpty()) { h.add(line); return; } if(h.peekFirst().first.longValue() <= a) { if(h.peekFirst().first.longValue() == a) { if(h.peekFirst().second.longValue() <= b) { return; } h.pollFirst(); } while(h.size() >= 2 && check(line, h.peekFirst(), h.get(1))) { h.pollFirst(); } h.add(line); } else { assert a <= h.peekLast().first.longValue(); if(h.peekLast().first.longValue() == a) { if(h.peekLast().second.longValue() <= b) { return; } h.pollLast(); } while(h.size() >= 2 && check(h.get(h.size() - 2), h.peekLast(), line)) { h.pollLast(); } h.add(line); } } private final long get(final IntPair p, final long x){ return p.first.longValue() * x + p.second.longValue(); } public final long query(final long x) { assert !isEmpty(); int l = -1, r = h.size() - 1; while(l + 1 < r) { int m = (l + r) >> 1; if(get(h.get(m), x) >= get(h.get(m + 1), x)) { l = m; } else { r = m; } } return isMin ? get(h.get(r), x) : -get(h.get(r), x); } public final long queryMonotoneInc(final long x) { assert !isEmpty(); while(h.size() >= 2 && get(h.peekFirst(), x) >= get(h.get(1), x)) { h.pollFirst(); } return isMin ? get(h.peekFirst(), x) : -get(h.peekFirst(), x); } public final long queryMonotoneDec(final long x) { assert !isEmpty(); while(h.size() >= 2 && get(h.peekLast(), x) >= get(h.get(h.size() - 2), x)) { h.pollLast(); } return isMin ? get(h.peekLast(), x) : -get(h.peekLast(), x); } }
Traceback (most recent call last): File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode() File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle raise RuntimeError('bundler is not specified: {}'.format(str(path))) RuntimeError: bundler is not specified: Java/library/ds/ConvexHullTrick.java