src/opt/smawk/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	24 / 0 / 24
Functions:	100.0%	4 / 0 / 4
Branches:	87.5%	14 / 0 / 16

    src/opt/smawk/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../util/alias/others/lib.hpp"
      
        namespace tifa_libs {
      
        //! $h(r) = argmin_i a_{r,i}$ MUST be non-decreasing
      
        // a: $[0, n) \times [0, m)$
      
        // @param f: f(u32, u32, u32) NE -> bool
      
        // f(r, x, y): $a_{r,x}\leq a_{r,y}$
      
        template <class Ft>
      
        35240
        CEXP vecu smawk(u32 n, u32 m, Ft&& f) NE {
      
        35240
          vecu ans(n);
      
        190423736
          auto g = [&](auto&& g, u32 u, u32 d, u32 l, u32 r) NE -> void {
      
          4/4void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 20465030 times.
✓ Branch 1 taken 20464989 times.
void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 74746838 times.
✓ Branch 1 taken 74711639 times.

        190388496
            if (u == d) return;
      
          2/4void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 20464989 times.
void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✗ Branch 0 not taken.
✓ Branch 1 taken 74711639 times.

        95176628
            assert(l < r);
      
        95176628
            cu32 rmid = (u + d) / 2;
      
        95176628
            u32 cm = l;
      
          4/4void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 203543567 times.
✓ Branch 1 taken 20464989 times.
void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 837160148 times.
✓ Branch 1 taken 74711639 times.

        1135880343
            flt_ (u32, col, l + 1, r)
      
          4/4void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 22338679 times.
✓ Branch 2 taken 181204888 times.
void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 412044282 times.
✓ Branch 2 taken 425115866 times.

        1040703715
              if (!f(rmid, cm, col)) cm = col;
      
        95176628
            ans[rmid] = cm, g(g, u, rmid, l, cm + 1), g(g, rmid + 1, d, cm, r);
      
          };
      
        35240
          g(g, 0, n, 0, m);
      
        35240
          return ans;
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../util/alias/others/lib.hpp"
4
5			namespace tifa_libs {
6
7			//! $h(r) = argmin_i a_{r,i}$ MUST be non-decreasing
8			// a: $[0, n) \times [0, m)$
9			// @param f: f(u32, u32, u32) NE -> bool
10			// f(r, x, y): $a_{r,x}\leq a_{r,y}$
11			template <class Ft>
12		35240	CEXP vecu smawk(u32 n, u32 m, Ft&& f) NE {
13		35240	vecu ans(n);
14		190423736	auto g = [&](auto&& g, u32 u, u32 d, u32 l, u32 r) NE -> void {
15	4/4 void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 0 taken 20465030 times. ✓ Branch 1 taken 20464989 times. void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 0 taken 74746838 times. ✓ Branch 1 taken 74711639 times.	190388496	if (u == d) return;
16	2/4 void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✗ Branch 0 not taken. ✓ Branch 1 taken 20464989 times. void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✗ Branch 0 not taken. ✓ Branch 1 taken 74711639 times.	95176628	assert(l < r);
17		95176628	cu32 rmid = (u + d) / 2;
18		95176628	u32 cm = l;
19	4/4 void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 0 taken 203543567 times. ✓ Branch 1 taken 20464989 times. void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 0 taken 837160148 times. ✓ Branch 1 taken 74711639 times.	1135880343	flt_ (u32, col, l + 1, r)
20	4/4 void tifa_libs::smawk<tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::conv_minplus_cv<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 1 taken 22338679 times. ✓ Branch 2 taken 181204888 times. void tifa_libs::smawk<tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}>(unsigned int, unsigned int, tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int, unsigned int)#1}&>(tifa_libs::larsch_2d<long, main::{lambda(unsigned int, unsigned int)#1}&>(unsigned int, main::{lambda(unsigned int, unsigned int)#1}&, long)::{lambda(unsigned int, unsigned int, unsigned int)#1}&&, unsigned int, unsigned int, unsigned int, unsigned int) const: ✓ Branch 1 taken 412044282 times. ✓ Branch 2 taken 425115866 times.	1040703715	if (!f(rmid, cm, col)) cm = col;
21		95176628	ans[rmid] = cm, g(g, u, rmid, l, cm + 1), g(g, rmid + 1, d, cm, r);
22			};
23		35240	g(g, 0, n, 0, m);
24		35240	return ans;
25			}
26
27			} // namespace tifa_libs
28