GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 90.2% 166 / 0 / 184
Functions: 54.5% 12 / 0 / 22
Branches: 71.9% 174 / 6 / 248
rmq.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <functional>
4 #include <vector>
5 #include <cassert>
6 #include <cstdint>
7
8 template <typename T, class Compare = std::less<T>> class RangeMinQuery : private Compare {
9 static const int BUCKET_SIZE = 32;
10 static const int BUCKET_SIZE_LOG = 5;
11 static_assert(BUCKET_SIZE == (1 << BUCKET_SIZE_LOG), "BUCKET_SIZE should be a power of 2");
12 static const int CACHE_LINE_ALIGNMENT = 64;
13 int n = 0;
14 std::vector<T> data;
15 std::vector<T> pref_data;
16 std::vector<T> suff_data;
17 std::vector<T> sparse_table;
18 std::vector<uint32_t> range_mask;
19
20 private:
21 35641617 int num_buckets() const {
22 16391717 return n >> BUCKET_SIZE_LOG;
23 }
24 673 int num_levels() const {
25
6/10
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::num_levels() const:
✓ Branch 5 → 6 taken 17 times.
✓ Branch 5 → 12 taken 12 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 17 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::num_levels() const:
✓ Branch 5 → 6 taken 17 times.
✓ Branch 5 → 12 taken 12 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 17 times.
RangeMinQuery<int, std::less<int> >::num_levels() const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 6 not taken.
 741 return num_buckets() ? 32 - __builtin_clz(num_buckets()) : 0;
26 }
27 74 int sparse_table_size() const {
28 148 return num_buckets() * num_levels();
29 }
30 private:
31
4/4
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
 22808520 const T& min(const T& a, const T& b) const {
32
8/12
None:
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
✓ Branch 45 → 46 taken 148581 times.
✓ Branch 45 → 47 taken 126619 times.
✓ Branch 221 → 222 taken 43 times.
✓ Branch 221 → 223 taken 49 times.
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::min(std::pair<int, int> const&, std::pair<int, int> const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
RangeMinQuery<int, std::less<int> >::min(int const&, int const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
 23083812 return Compare::operator()(a, b) ? a : b;
33 }
34
6/6
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
 66240937 void setmin(T& a, const T& b) const {
35
10/14
None:
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::setmin(std::pair<int, int>&, std::pair<int, int> const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
✓ Branch 7 → 8 taken 112584 times.
✓ Branch 7 → 10 taken 120600 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::setmin(std::pair<int, int>&, std::pair<int, int> const&) const:
✓ Branch 7 → 8 taken 103194 times.
✓ Branch 7 → 10 taken 129990 times.
RangeMinQuery<int, std::less<int> >::setmin(int&, int const&) const:
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
 51319360 if (Compare::operator()(b, a)) a = b;
36 466368 }
37
38 148 template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
39
40 public:
41
1/1
✓ Branch 12 → 13 taken 25 times.
 25 RangeMinQuery() {}
42
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 52 times.
 74 template <typename Vec> explicit RangeMinQuery(const Vec& data_, const Compare& comp_ = Compare())
43 : Compare(comp_)
44 74 , n(get_size(data_))
45
2/3
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 16 → 17 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 16 → 17 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✗ Branch 5 → 6 not taken.
 74 , data(n)
46
3/4
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 24 → 25 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 24 → 25 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 5 → 6 taken 52 times.
✗ Branch 9 → 10 not taken.
 74 , pref_data(n)
47
3/4
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 32 → 33 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 32 → 33 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 6 → 7 taken 52 times.
✗ Branch 13 → 14 not taken.
 74 , suff_data(n)
48
5/7
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 40 → 41 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 40 → 41 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 7 → 8 taken 40 times.
✓ Branch 7 → 9 taken 12 times.
✓ Branch 9 → 10 taken 52 times.
✗ Branch 17 → 18 not taken.
✗ Branch 18 → 19 not taken.
 114 , sparse_table(sparse_table_size())
49
3/4
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 48 → 49 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 48 → 49 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 10 → 11 taken 52 times.
✗ Branch 22 → 23 not taken.
 74 , range_mask(n)
50 {
51
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 63 → 51 taken 897 times.
✓ Branch 63 → 104 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 63 → 51 taken 897 times.
✓ Branch 63 → 104 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 13 → 12 taken 17337442 times.
✓ Branch 13 → 22 taken 52 times.
✗ Branch 28 → 25 not taken.
✗ Branch 28 → 29 not taken.
 17339310 for (int i = 0; i < n; i++) data[i] = data_[i];
52
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 106 → 64 taken 897 times.
✓ Branch 106 → 132 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 106 → 64 taken 897 times.
✓ Branch 106 → 132 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 22 → 14 taken 17337442 times.
✓ Branch 22 → 27 taken 52 times.
✗ Branch 47 → 30 not taken.
✗ Branch 47 → 48 not taken.
 17339310 for (int i = 0; i < n; i++) {
53
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 64 → 65 taken 861 times.
✓ Branch 64 → 96 taken 36 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 64 → 65 taken 861 times.
✓ Branch 64 → 96 taken 36 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 14 → 15 taken 16795629 times.
✓ Branch 14 → 20 taken 541813 times.
✗ Branch 30 → 31 not taken.
✗ Branch 30 → 44 not taken.
 17339236 if (i & (BUCKET_SIZE-1)) {
54 16797351 uint32_t m = range_mask[i-1];
55
12/18
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 72 → 73 taken 1526 times.
✓ Branch 72 → 88 taken 101 times.
✓ Branch 87 → 88 taken 760 times.
✓ Branch 87 → 95 taken 766 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 72 → 73 taken 1542 times.
✓ Branch 72 → 88 taken 83 times.
✓ Branch 87 → 88 taken 778 times.
✓ Branch 87 → 95 taken 764 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 16 → 17 taken 25728620 times.
✓ Branch 16 → 19 taken 1744471 times.
✓ Branch 17 → 18 taken 10677462 times.
✓ Branch 17 → 19 taken 15051158 times.
✗ Branch 34 → 35 not taken.
✗ Branch 34 → 40 not taken.
✗ Branch 38 → 39 not taken.
✗ Branch 38 → 40 not taken.
✗ Branch 41 → 33 not taken.
✗ Branch 41 → 42 not taken.
 27479411 while (m && !Compare::operator()(data[(i | (BUCKET_SIZE-1)) - __builtin_clz(m)], data[i])) {
56 10678992 m -= uint32_t(1) << (BUCKET_SIZE - 1 - __builtin_clz(m));
57 }
58 16797351 m |= uint32_t(1) << (i & (BUCKET_SIZE - 1));
59 16797351 range_mask[i] = m;
60 } else {
61 541885 range_mask[i] = 1;
62 }
63 }
64
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 134 → 107 taken 897 times.
✓ Branch 134 → 135 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 134 → 107 taken 897 times.
✓ Branch 134 → 135 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 27 → 23 taken 17337442 times.
✓ Branch 27 → 28 taken 52 times.
✗ Branch 56 → 49 not taken.
✗ Branch 56 → 57 not taken.
 17339310 for (int i = 0; i < n; i++) {
65
2/2
✓ Branch 23 → 24 taken 16795629 times.
✓ Branch 23 → 26 taken 541813 times.
 17339236 pref_data[i] = data[i];
66
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 118 → 119 taken 861 times.
✓ Branch 118 → 131 taken 36 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 118 → 119 taken 861 times.
✓ Branch 118 → 131 taken 36 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 23 → 24 taken 16795629 times.
✓ Branch 23 → 26 taken 541813 times.
✗ Branch 51 → 52 not taken.
✗ Branch 51 → 55 not taken.
 17339236 if (i & (BUCKET_SIZE-1)) {
67
2/2
✓ Branch 24 → 25 taken 15051158 times.
✓ Branch 24 → 26 taken 1744471 times.
 32390322 setmin(pref_data[i], pref_data[i-1]);
68 }
69 }
70
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 166 → 138 taken 897 times.
✓ Branch 166 → 194 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 166 → 138 taken 897 times.
✓ Branch 166 → 194 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 34 → 29 taken 17337442 times.
✓ Branch 34 → 41 taken 52 times.
✗ Branch 66 → 58 not taken.
✗ Branch 66 → 67 not taken.
 17339310 for (int i = n-1; i >= 0; i--) {
71
2/2
✓ Branch 29 → 30 taken 17337390 times.
✓ Branch 29 → 33 taken 52 times.
 17339236 suff_data[i] = data[i];
72
12/16
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 151 → 152 taken 886 times.
✓ Branch 151 → 165 taken 11 times.
✓ Branch 152 → 153 taken 861 times.
✓ Branch 152 → 165 taken 25 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 151 → 152 taken 886 times.
✓ Branch 151 → 165 taken 11 times.
✓ Branch 152 → 153 taken 861 times.
✓ Branch 152 → 165 taken 25 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 29 → 30 taken 17337390 times.
✓ Branch 29 → 33 taken 52 times.
✓ Branch 30 → 31 taken 16795629 times.
✓ Branch 30 → 33 taken 541761 times.
✗ Branch 60 → 61 not taken.
✗ Branch 60 → 65 not taken.
✗ Branch 61 → 62 not taken.
✗ Branch 61 → 65 not taken.
 17339236 if (i+1 < n && ((i+1) & (BUCKET_SIZE-1))) {
73
2/2
✓ Branch 31 → 32 taken 10633161 times.
✓ Branch 31 → 33 taken 6162468 times.
 27972325 setmin(suff_data[i], suff_data[i+1]);
74 }
75 }
76
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 197 → 167 taken 26 times.
✓ Branch 197 → 239 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 197 → 167 taken 26 times.
✓ Branch 197 → 239 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 41 → 35 taken 541786 times.
✓ Branch 41 → 46 taken 52 times.
✗ Branch 78 → 68 not taken.
✗ Branch 78 → 79 not taken.
 541986 for (int i = 0; i < num_buckets(); i++) {
77 541838 sparse_table[i] = data[i * BUCKET_SIZE];
78
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 192 → 179 taken 806 times.
✓ Branch 192 → 193 taken 26 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 192 → 179 taken 806 times.
✓ Branch 192 → 193 taken 26 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 39 → 36 taken 16795366 times.
✓ Branch 39 → 40 taken 541786 times.
✗ Branch 75 → 71 not taken.
✗ Branch 75 → 76 not taken.
 17338816 for (int v = 1; v < BUCKET_SIZE; v++) {
79
2/2
✓ Branch 36 → 37 taken 1700391 times.
✓ Branch 36 → 38 taken 15094975 times.
 18497369 setmin(sparse_table[i], data[i * BUCKET_SIZE + v]);
80 }
81 }
82
8/10
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✓ Branch 241 → 233 taken 7 times.
✓ Branch 241 → 242 taken 11 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✓ Branch 241 → 233 taken 7 times.
✓ Branch 241 → 242 taken 11 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 46 → 47 taken 551 times.
✓ Branch 46 → 48 taken 12 times.
✓ Branch 48 → 45 taken 511 times.
✓ Branch 48 → 49 taken 52 times.
✗ Branch 93 → 80 not taken.
✗ Branch 93 → 94 not taken.
 1150 for (int l = 0; l+1 < num_levels(); l++) {
83
8/12
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✗ Branch 233 → 234 not taken.
✓ Branch 233 → 235 taken 53 times.
✓ Branch 238 → 198 taken 46 times.
✓ Branch 238 → 239 taken 7 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✗ Branch 233 → 234 not taken.
✓ Branch 233 → 235 taken 53 times.
✓ Branch 238 → 198 taken 46 times.
✓ Branch 238 → 239 taken 7 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 45 → 42 taken 6416463 times.
✓ Branch 45 → 46 taken 511 times.
✗ Branch 90 → 81 not taken.
✗ Branch 90 → 91 not taken.
 6417186 for (int i = 0; i + (1 << (l+1)) <= num_buckets(); i++) {
84
4/6
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::less<std::pair<int, int> > const&):
✗ Branch 202 → 203 not taken.
✓ Branch 202 → 204 taken 46 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::RangeMinQuery<std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >(std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > const&, std::greater<std::pair<int, int> > const&):
✗ Branch 202 → 203 not taken.
✓ Branch 202 → 204 taken 46 times.
RangeMinQuery<int, std::less<int> >::RangeMinQuery<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> > const&, std::less<int> const&):
✓ Branch 42 → 43 taken 2757611 times.
✓ Branch 42 → 44 taken 3658852 times.
 9174534 sparse_table[(l+1) * num_buckets() + i] = min(sparse_table[l * num_buckets() + i], sparse_table[l * num_buckets() + i + (1 << l)]);
85 }
86 }
87 74 }
88
89 16806956 T query(int l, int r) const {
90 16806956 assert(l <= r);
91 16806956 int bucket_l = (l >> BUCKET_SIZE_LOG);
92 16806956 int bucket_r = (r >> BUCKET_SIZE_LOG);
93
6/8
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✓ Branch 4 → 5 taken 14171 times.
✗ Branch 4 → 8 not taken.
✓ Branch 4 → 25 taken 137600 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✓ Branch 4 → 5 taken 14171 times.
✓ Branch 4 → 25 taken 137600 times.
RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 4 → 5 taken 386649 times.
✓ Branch 4 → 6 taken 16116765 times.
✗ Branch 4 → 8 not taken.
 16806956 if (bucket_l == bucket_r) {
94 414991 uint32_t msk = range_mask[r] & ~((uint32_t(1) << (l & (BUCKET_SIZE-1))) - 1);
95
2/4
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 14171 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 14171 times.
 414991 int ind = (l & ~(BUCKET_SIZE-1)) + __builtin_ctz(msk);
96 414991 return data[ind];
97 } else {
98
2/3
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 10 → 11 not taken.
RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 6 → 7 taken 7636595 times.
✓ Branch 6 → 8 taken 8480170 times.
 16667165 T ans = min(suff_data[l], pref_data[r]);
99 16391965 bucket_l++;
100
6/10
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 18 not taken.
✓ Branch 49 → 50 taken 115328 times.
✓ Branch 49 → 78 taken 22272 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✓ Branch 49 → 50 taken 115328 times.
✓ Branch 49 → 78 taken 22272 times.
RangeMinQuery<int, std::less<int> >::query(int, int) const:
✓ Branch 8 → 9 taken 15387945 times.
✓ Branch 8 → 10 taken 728820 times.
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 18 not taken.
 16391965 if (bucket_l < bucket_r) {
101
2/4
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 50 → 51 not taken.
✓ Branch 50 → 52 taken 115328 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 50 → 51 not taken.
✓ Branch 50 → 52 taken 115328 times.
 15618601 int level = (32 - __builtin_clz(bucket_r - bucket_l)) - 1;
102
0/1
✗ Branch 14 → 15 not taken.
 15849257 setmin(ans, sparse_table[level * num_buckets() + bucket_l]);
103
2/5
RangeMinQuery<std::pair<int, int>, std::less<std::pair<int, int> > >::query(int, int) const:
✗ Branch 17 → 18 not taken.
✗ Branch 70 → 71 not taken.
✓ Branch 70 → 72 taken 115328 times.
RangeMinQuery<std::pair<int, int>, std::greater<std::pair<int, int> > >::query(int, int) const:
✗ Branch 70 → 71 not taken.
✓ Branch 70 → 72 taken 115328 times.
 16578077 setmin(ans, sparse_table[level * num_buckets() + bucket_r - (1 << level)]);
104 }
105 275200 return ans;
106 }
107 }
108 };
109
110 template <typename T> using RangeMaxQuery = RangeMinQuery<T, std::greater<T>>;
111