/tmp/solutions/build/range_reverse_range_sum-slow.cpp:
1| |#include <common.h>
2| |prelude;
3| |
4| |namespace {
5| |
6| |constexpr int N = 200001;
7| |
8| |struct Node {
9| | int pri;
10| | int val;
11| | u64 sum;
12| | int rev;
13| | int size;
14| | int l, r;
15| |} node[N];
16| |
17| 168M|def maintain(int x) -> void {
18| 168M| node[x].size = node[node[x].l].size + 1 + node[node[x].r].size;
19| 168M| node[x].sum = node[node[x].l].sum + node[x].val + node[node[x].r].sum;
20| 168M|}
21| |
22| 169M|def pushdown(int x) -> void {
23| 169M| if (node[x].rev) {
------------------
| Branch (23:7): [True: 25.07%, False: 74.93%]
------------------
24| 42.5M| std::swap(node[x].l, node[x].r);
25| 42.5M| node[node[x].l].rev ^= 1;
26| 42.5M| node[node[x].r].rev ^= 1;
27| 42.5M| node[x].rev = 0;
28| 42.5M| }
29| 169M|}
30| |
31| 1.13M|def reverse(int x) -> void {
32| 1.13M| if (x == 0) return;
^115k
------------------
| Branch (32:7): [True: 10.25%, False: 89.75%]
------------------
33| 1.01M| node[x].rev ^= 1;
34| 1.01M| pushdown(x);
35| 1.01M|}
36| |
37| 96.1M|def merge(int x, int y) -> int {
38| 96.1M| if (x == 0) return y;
^3.31M
------------------
| Branch (38:7): [True: 3.45%, False: 96.55%]
------------------
39| 92.8M| if (y == 0) return x;
^2.92M
------------------
| Branch (39:7): [True: 3.15%, False: 96.85%]
------------------
40| 89.9M| if (node[x].pri > node[y].pri) {
------------------
| Branch (40:7): [True: 58.59%, False: 41.41%]
------------------
41| 52.6M| pushdown(x);
42| 52.6M| node[x].r = merge(node[x].r, y);
43| 52.6M| maintain(x);
44| 52.6M| return x;
45| 52.6M| } else {
46| 37.2M| pushdown(y);
47| 37.2M| node[y].l = merge(x, node[y].l);
48| 37.2M| maintain(y);
49| 37.2M| return y;
50| 37.2M| }
51| 89.9M|}
52| |
53| 83.4M|def split(int x, int k) -> std::pair<int, int> {
54| 83.4M| if (x == 0) return {0, 0};
^4.52M
------------------
| Branch (54:7): [True: 5.42%, False: 94.58%]
------------------
55| 78.9M| pushdown(x);
56| 78.9M| if (int size = node[node[x].l].size; k <= size) {
------------------
| Branch (56:40): [True: 51.27%, False: 48.73%]
------------------
57| 40.4M| let[a, b] = split(node[x].l, k);
58| 40.4M| node[x].l = b;
59| 40.4M| maintain(x);
60| 40.4M| return {a, x};
61| 40.4M| } else {
62| 38.4M| let[a, b] = split(node[x].r, k - size - 1);
63| 38.4M| node[x].r = a;
64| 38.4M| maintain(x);
65| 38.4M| return {x, b};
66| 38.4M| }
67| 78.9M|}
68| |
69| |} // namespace
70| |
71| 20|int main() {
72| 20| rd rd;
73| 20| wt wt;
74| 20| int n = rd.uh();
75| 20| int q = rd.uh();
76| 20|#ifdef LOCAL
77| 20| std::memset(node, 0, sizeof(Node) * (n + 1));
78| 20|#endif
79| 20| int x = 0;
80| 1.71M| for (int i = 1; i <= n; ++i) {
^1.71M
------------------
| Branch (80:19): [True: 100.00%, False: 0.00%]
------------------
81| 1.71M| node[i].size = 1;
82| 1.71M| node[i].pri = node[i].sum = node[i].val = rd.uw();
83| 1.71M| x = merge(x, i);
84| 1.71M| }
85| 20| if (n == 0) rd.skip(1);
^3
------------------
| Branch (85:7): [True: 15.00%, False: 85.00%]
------------------
86| 2.26M| while (q--) {
------------------
| Branch (86:10): [True: 100.00%, False: 0.00%]
------------------
87| 2.26M| int t = rd.u1();
88| 2.26M| int l = rd.uh();
89| 2.26M| int r = rd.uh();
90| 2.26M| let[a, b] = split(x, l);
91| 2.26M| let[c, d] = split(b, r - l);
92| 2.26M| if (t == 0) {
------------------
| Branch (92:9): [True: 49.99%, False: 50.01%]
------------------
93| 1.13M| reverse(c);
94| 1.13M| }
95| 2.26M| if (t == 1) {
------------------
| Branch (95:9): [True: 50.01%, False: 49.99%]
------------------
96| 1.13M| wt.ud(node[c].sum);
97| 1.13M| }
98| 2.26M| x = merge(a, merge(c, d));
99| 2.26M| }
100| 20| return 0;
101| 20|}