/tmp/solutions/build/predecessor_problem-main.cpp:
1| |#include <common.h>
2| |prelude;
3| |
4| |namespace {
5| |
6| |u64 root;
7| |u64 lv18[39];
8| |u64 lv12[2442];
9| |u64 leaf[156250];
10| |
11| 1.26M|void set(u32 x) {
12| 1.26M| leaf[x >> 6] |= 1ull << (x & 63);
13| 1.26M| lv12[x >> 12] |= 1ull << ((x >> 6) & 63);
14| 1.26M| lv18[x >> 18] |= 1ull << ((x >> 12) & 63);
15| 1.26M| root |= 1ull << (x >> 18);
16| 1.26M|}
17| |
18| 1.76M|void unset(u32 x) {
19| 1.76M| if (!(leaf[x >> 6] &= ~(1ull << (x & 63))))
------------------
| Branch (19:7): [True: 0.25%, False: 99.75%]
------------------
20| 4.36k| if (!(lv12[x >> 12] &= ~(1ull << ((x >> 6) & 63))))
------------------
| Branch (20:9): [True: 0.07%, False: 99.93%]
------------------
21| 3| if (!(lv18[x >> 18] &= ~(1ull << ((x >> 12) & 63))))
------------------
| Branch (21:11): [True: 0.00%, False: 100.00%]
------------------
22| 0| root &= ~(1ull << (x >> 18));
23| 1.76M|}
24| |
25| 2.44M|bool get(u32 x) { return leaf[x >> 6] & (1ull << (x & 63)); }
26| |
27| 2.77M|u32 nxt(u32 x) {
28| 2.77M| if (u64 tmp = leaf[x >> 6] & (-1ull << (x & 63)); !tmp) {
------------------
| Branch (28:53): [True: 60.66%, False: 39.34%]
------------------
29| 1.68M| if (u64 tmp = lv12[x >> 12] & (-2ull << ((x >> 6) & 63)); !tmp) {
------------------
| Branch (29:63): [True: 99.31%, False: 0.69%]
------------------
30| 1.66M| if (u64 tmp = lv18[x >> 18] & (-2ull << ((x >> 12) & 63)); !tmp) {
------------------
| Branch (30:66): [True: 95.22%, False: 4.78%]
------------------
31| 1.58M| if (u64 tmp = root & (-2ull << (x >> 18)); !tmp) {
------------------
| Branch (31:52): [True: 50.84%, False: 49.16%]
------------------
32| 808k| return -1;
33| 808k| } else {
34| 781k| u32 ans = __builtin_ctzll(tmp);
35| 781k| ans = ans << 6 | __builtin_ctzll(lv18[ans]);
36| 781k| ans = ans << 6 | __builtin_ctzll(lv12[ans]);
37| 781k| ans = ans << 6 | __builtin_ctzll(leaf[ans]);
38| 781k| return ans;
39| 781k| }
40| 1.58M| } else {
41| 79.7k| u32 ans = (x >> 18) << 6 | __builtin_ctzll(tmp);
42| 79.7k| ans = ans << 6 | __builtin_ctzll(lv12[ans]);
43| 79.7k| ans = ans << 6 | __builtin_ctzll(leaf[ans]);
44| 79.7k| return ans;
45| 79.7k| }
46| 1.66M| } else {
47| 11.6k| u32 ans = (x >> 12) << 6 | __builtin_ctzll(tmp);
48| 11.6k| ans = ans << 6 | __builtin_ctzll(leaf[ans]);
49| 11.6k| return ans;
50| 11.6k| }
51| 1.68M| } else {
52| 1.09M| u32 ans = (x >> 6) << 6 | __builtin_ctzll(tmp);
53| 1.09M| return ans;
54| 1.09M| }
55| 2.77M|}
56| |
57| 2.77M|u32 pre(u32 x) {
58| 2.77M| if (u64 tmp = leaf[x >> 6] & ~(-2ull << (x & 63)); !tmp) {
------------------
| Branch (58:54): [True: 60.68%, False: 39.32%]
------------------
59| 1.68M| if (u64 tmp = lv12[x >> 12] & ~(-1ull << ((x >> 6) & 63)); !tmp) {
------------------
| Branch (59:64): [True: 99.34%, False: 0.66%]
------------------
60| 1.66M| if (u64 tmp = lv18[x >> 18] & ~(-1ull << ((x >> 12) & 63)); !tmp) {
------------------
| Branch (60:67): [True: 93.95%, False: 6.05%]
------------------
61| 1.56M| if (u64 tmp = root & ~(-1ull << (x >> 18)); !tmp) {
------------------
| Branch (61:53): [True: 49.81%, False: 50.19%]
------------------
62| 781k| return -1;
63| 787k| } else {
64| 787k| u32 ans = 63 - __builtin_clzll(tmp);
65| 787k| ans = ans << 6 | 63 - __builtin_clzll(lv18[ans]);
66| 787k| ans = ans << 6 | 63 - __builtin_clzll(lv12[ans]);
67| 787k| ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
68| 787k| return ans;
69| 787k| }
70| 1.56M| } else {
71| 100k| u32 ans = (x >> 18) << 6 | 63 - __builtin_clzll(tmp);
72| 100k| ans = ans << 6 | 63 - __builtin_clzll(lv12[ans]);
73| 100k| ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
74| 100k| return ans;
75| 100k| }
76| 1.66M| } else {
77| 11.0k| u32 ans = (x >> 12) << 6 | 63 - __builtin_clzll(tmp);
78| 11.0k| ans = ans << 6 | 63 - __builtin_clzll(leaf[ans]);
79| 11.0k| return ans;
80| 11.0k| }
81| 1.68M| } else {
82| 1.08M| u32 ans = (x >> 6) << 6 | 63 - __builtin_clzll(tmp);
83| 1.08M| return ans;
84| 1.08M| }
85| 2.77M|}
86| |
87| |} // namespace
88| |
89| 22|int main() {
90| 22| rd rd;
91| 22| wt wt;
92| 22| int n = rd.uh();
93| 22| int q = rd.uh();
94| 22|#ifdef LOCAL
95| 22| root = 0;
96| 22| std::memset(lv18, 0, sizeof(lv18));
97| 22| std::memset(lv12, 0, sizeof(lv12));
98| 22| std::memset(leaf, 0, sizeof(leaf));
99| 22|#endif
100| 22| int i = 0;
101| 1.56M| for (; i + 64 < n; i += 64) {
^1.56M
------------------
| Branch (101:10): [True: 100.00%, False: 0.00%]
------------------
102| 1.56M| u32 a = _mm256_movemask_epi8(_mm256_cmpeq_epi8(
103| 1.56M| _mm256_loadu_si256(reinterpret_cast<const __m256i_u *>(rd.p + i)),
104| 1.56M| _mm256_set1_epi8('1')));
105| 1.56M| u32 b = _mm256_movemask_epi8(_mm256_cmpeq_epi8(
106| 1.56M| _mm256_loadu_si256(reinterpret_cast<const __m256i_u *>(rd.p + i + 32)),
107| 1.56M| _mm256_set1_epi8('1')));
108| 1.56M| leaf[i >> 6] = a | u64(b) << 32;
109| 1.56M| }
110| 1.17k| for (; i < n; ++i) leaf[i >> 6] |= u64(rd.p[i] - '0') << (i & 63);
^1.15k^1.15k
------------------
| Branch (110:10): [True: 98.13%, False: 1.87%]
------------------
111| 1.56M| for (int i = 0; i <= (n - 1) / 64; ++i)
^1.56M
------------------
| Branch (111:19): [True: 100.00%, False: 0.00%]
------------------
112| 1.56M| lv12[i >> 6] |= u64(!!leaf[i]) << (i & 63);
113| 24.4k| for (int i = 0; i <= (n - 1) / 64 / 64; ++i)
^24.4k
------------------
| Branch (113:19): [True: 99.91%, False: 0.09%]
------------------
114| 24.4k| lv18[i >> 6] |= u64(!!lv12[i]) << (i & 63);
115| 424| for (int i = 0; i <= (n - 1) / 64 / 64 / 64; ++i)
^402
------------------
| Branch (115:19): [True: 94.81%, False: 5.19%]
------------------
116| 402| root |= u64(!!lv18[i]) << (i & 63);
117| 22| rd.p += n + 1;
118| 11.0M| while (q--) {
------------------
| Branch (118:10): [True: 100.00%, False: 0.00%]
------------------
119| 11.0M| let t = rd.u1();
120| 11.0M| let k = rd.uh();
121| 11.0M| if (t == 0) {
------------------
| Branch (121:9): [True: 11.48%, False: 88.52%]
------------------
122| 1.26M| set(k);
123| 1.26M| }
124| 11.0M| if (t == 1) {
------------------
| Branch (124:9): [True: 16.06%, False: 83.94%]
------------------
125| 1.76M| unset(k);
126| 1.76M| }
127| 11.0M| if (t == 2) {
------------------
| Branch (127:9): [True: 22.15%, False: 77.85%]
------------------
128| 2.44M| let x = get(k);
129| 2.44M| wt.uw(x);
130| 2.44M| }
131| 11.0M| if (t == 3) {
------------------
| Branch (131:9): [True: 25.16%, False: 74.84%]
------------------
132| 2.77M| let x = nxt(k);
133| 2.77M| if (~x) {
------------------
| Branch (133:11): [True: 70.84%, False: 29.16%]
------------------
134| 1.96M| wt.uw(x);
135| 1.96M| } else {
136| 808k| wt.puts(" -1", 3);
137| 808k| }
138| 2.77M| }
139| 11.0M| if (t == 4) {
------------------
| Branch (139:9): [True: 25.15%, False: 74.85%]
------------------
140| 2.77M| let x = pre(k);
141| 2.77M| if (~x) {
------------------
| Branch (141:11): [True: 71.79%, False: 28.21%]
------------------
142| 1.98M| wt.uw(x);
143| 1.98M| } else {
144| 781k| wt.puts(" -1", 3);
145| 781k| }
146| 2.77M| }
147| 11.0M| }
148| 22| return 0;
149| 22|}