src/opt/lis/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 INDEX of LIS in @a | ||
| 8 | template <class T, class C = std::less<T>> | ||
| 9 | 57 | CEXP vecu lis(vec<T> CR a, T inf = std::numeric_limits<T>::max(), C&& comp = C{}) NE { | |
| 10 | 114 | vec<T> f{inf}; | |
| 11 | 57 | vecu g; | |
| 12 |
2/2✓ Branch 5 taken 6756776 times.
✓ Branch 6 taken 57 times.
|
6756833 | for (auto i : a) { |
| 13 | 6756776 | auto it = lower_bound(f, i, comp); | |
| 14 | 6756776 | g.push_back(u32(it - begin(f))); | |
| 15 |
2/2✓ Branch 2 taken 725302 times.
✓ Branch 3 taken 6031474 times.
|
6756776 | if (it == end(f)) f.push_back(i); |
| 16 | 6031474 | else *it = i; | |
| 17 | } | ||
| 18 | 57 | T val = inf; | |
| 19 | 57 | vecu ret; | |
| 20 |
2/2✓ Branch 2 taken 6756776 times.
✓ Branch 3 taken 57 times.
|
6756833 | for (u32 i = u32(g.size() - 1), now = u32(f.size() - 1); ~i; --i) |
| 21 |
5/6✓ Branch 1 taken 725359 times.
✓ Branch 2 taken 6031417 times.
✓ Branch 4 taken 725359 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 725359 times.
✓ Branch 7 taken 6031417 times.
|
6756776 | if (g[i] == now && val > a[i]) ret.push_back((u32)i), --now, val = a[i]; |
| 22 | 57 | reverse(ret); | |
| 23 | 57 | return ret; | |
| 24 | 57 | } | |
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |