test/cpv_local/math/simpson.bzoj2731.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/2731 | ||
| 2 | |||
| 3 | #include "../../../src/edh/discretization/lib.hpp" | ||
| 4 | #include "../../../src/math/simpson/lib.hpp" | ||
| 5 | |||
| 6 | using namespace tifa_libs; | ||
| 7 | using std::cin, std::cout; | ||
| 8 | using data_t = f128; | ||
| 9 | struct Node { | ||
| 10 | int x, y, m; | ||
| 11 | 22966 | Node(int x = 0, int y = 0, int m = 0) : x(x), y(y), m(m) {} | |
| 12 | }; | ||
| 13 | |||
| 14 | vec<Node> v; | ||
| 15 | vecpt<data_t> seg; | ||
| 16 | template <class T> | ||
| 17 | 2127276 | T f(T pos) { | |
| 18 | 2127276 | seg.clear(); | |
| 19 |
2/2✓ Branch 5 taken 3621699772 times.
✓ Branch 6 taken 2127276 times.
|
3623827048 | for (auto [x, y, m] : v) |
| 20 |
5/6✓ Branch 0 taken 1605830336 times.
✓ Branch 1 taken 2015869436 times.
✓ Branch 2 taken 69011252 times.
✓ Branch 3 taken 1536819084 times.
✓ Branch 5 taken 69011252 times.
✗ Branch 6 not taken.
|
3621699772 | if (x < pos && pos < x + m) seg.emplace_back(y, x + y + m - pos); |
| 21 |
2/2✓ Branch 1 taken 352 times.
✓ Branch 2 taken 2126924 times.
|
2127276 | if (seg.empty()) return 0; |
| 22 |
1/2✓ Branch 1 taken 2126924 times.
✗ Branch 2 not taken.
|
2126924 | std::ranges::sort(seg); |
| 23 | 2126924 | data_t ans = 0, lst = seg.front().first; | |
| 24 |
2/2✓ Branch 7 taken 69011252 times.
✓ Branch 8 taken 2126924 times.
|
71138176 | for (auto&& [l, r] : seg) |
| 25 |
2/2✓ Branch 0 taken 49811898 times.
✓ Branch 1 taken 19199354 times.
|
69011252 | if (r - lst > 0) { |
| 26 | 49811898 | ans += r - std::max(l, lst); | |
| 27 | 49811898 | lst = r; | |
| 28 | } | ||
| 29 | 2126924 | return (T)ans; | |
| 30 | } | ||
| 31 | |||
| 32 | CEXP data_t EPS = 1e-10l; | ||
| 33 | |||
| 34 | 10 | int main() { | |
| 35 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cout << std::fixed << std::setprecision(1); |
| 36 | |||
| 37 | u32 n; | ||
| 38 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cin >> n; |
| 39 | 10 | v.clear(); | |
| 40 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vec<Node> v_(n); |
| 41 |
5/8✓ Branch 4 taken 22966 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 22966 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 22966 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 22966 times.
✓ Branch 15 taken 10 times.
|
22976 | for (auto& [x, y, m] : v_) cin >> y >> x >> m; |
| 42 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
324234 | std::ranges::sort(v_, [](Node CR l, Node CR r) { return l.m > r.m; }); |
| 43 |
1/2✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
|
10 | v.push_back(v_.front()); |
| 44 |
2/2✓ Branch 0 taken 22947 times.
✓ Branch 1 taken 6 times.
|
22953 | flt_ (u32, i, 1, n) { |
| 45 | 22947 | auto&& now = v_[i]; | |
| 46 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 22943 times.
|
22947 | if (now.m == 0) break; |
| 47 |
14/16✓ Branch 1 taken 22943 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4973 times.
✓ Branch 4 taken 17970 times.
✓ Branch 6 taken 4973 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2760616 times.
✓ Branch 9 taken 1400472 times.
✓ Branch 10 taken 865695 times.
✓ Branch 11 taken 1894921 times.
✓ Branch 12 taken 800117 times.
✓ Branch 13 taken 65578 times.
✓ Branch 14 taken 302398 times.
✓ Branch 15 taken 497719 times.
✓ Branch 16 taken 17970 times.
✓ Branch 17 taken 284428 times.
|
4184031 | if (std::ranges::none_of(v, [&now](Node CR x) { return now.x >= x.x && now.x + now.m <= x.x + x.m && now.y >= x.y && now.y + now.m <= x.y + x.m && now.x + now.y + now.m <= x.x + x.y + x.m; })) v.push_back(now); |
| 48 | } | ||
| 49 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | seg.reserve(n); |
| 50 | |||
| 51 | 10 | vec<int> pos; | |
| 52 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | pos.reserve(n * 2); |
| 53 |
2/2✓ Branch 4 taken 4983 times.
✓ Branch 5 taken 10 times.
|
4993 | for (auto&& [x, _, m] : v) { |
| 54 |
1/2✓ Branch 1 taken 4983 times.
✗ Branch 2 not taken.
|
4983 | pos.push_back(x); |
| 55 |
1/2✓ Branch 1 taken 4983 times.
✗ Branch 2 not taken.
|
4983 | pos.push_back(x + m); |
| 56 | } | ||
| 57 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | pos = uniq(pos); |
| 58 | 10 | data_t ans = 0; | |
| 59 | simpson_impl<f64, f<f64>> integral; | ||
| 60 | |||
| 61 |
2/2✓ Branch 4 taken 9302 times.
✓ Branch 5 taken 10 times.
|
9312 | flt_ (u32, i, 1, (u32)pos.size()) ans += integral(f64(pos[i - 1] + EPS), f64(pos[i] - 2 * EPS), (f64)EPS); |
| 62 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | cout << ans << '\n'; |
| 63 | 10 | } | |
| 64 |