src/opt/hoverline/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // @return {l, r} s.t. $\forall x\in[l_i,r_i],~a_x\geq a_i$, $l_i$ leftmost, $r_i$ rightmost | ||
| 8 | template <class T, class C = std::less<T>> | ||
| 9 | 26241 | CEXP ptt<vecu> hoverline(vec<T> CR a, C&& comp = C{}) NE { | |
| 10 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 26241 times.
|
26241 | if (a.empty()) return {{}, {}}; |
| 11 | 26241 | vecu l(a.size()); | |
| 12 | 26241 | std::iota(begin(l), end(l), 0_u32); | |
| 13 | 26241 | auto r = l; | |
| 14 |
2/2✓ Branch 1 taken 24621411 times.
✓ Branch 2 taken 26241 times.
|
24647652 | flt_ (u32, i, 0, (u32)a.size()) |
| 15 |
6/6✓ Branch 4 taken 34840689 times.
✓ Branch 5 taken 14230480 times.
✓ Branch 10 taken 24449758 times.
✓ Branch 11 taken 10390931 times.
✓ Branch 12 taken 24449758 times.
✓ Branch 13 taken 24621411 times.
|
49071169 | while (l[i] && !comp(a[l[i] - 1], a[i])) l[i] = l[l[i] - 1]; |
| 16 |
2/2✓ Branch 1 taken 24595170 times.
✓ Branch 2 taken 26241 times.
|
24621411 | for (u32 i = (u32)a.size() - 2; ~i; --i) |
| 17 |
6/6✓ Branch 5 taken 34752373 times.
✓ Branch 6 taken 14136409 times.
✓ Branch 11 taken 24293612 times.
✓ Branch 12 taken 10458761 times.
✓ Branch 13 taken 24293612 times.
✓ Branch 14 taken 24595170 times.
|
48888782 | while ((i32)r[i] < (i32)a.size() - 1 && !comp(a[r[i] + 1], a[i])) r[i] = r[r[i] + 1]; |
| 18 | 26241 | return {l, r}; | |
| 19 | 26241 | } | |
| 20 | |||
| 21 | } // namespace tifa_libs | ||
| 22 |