/tmp/solutions/build/staticrmq-main.cpp:
1| |#include <common.h>
2| |#include <toy/bit.h>
3| |prelude;
4| |
5| 27|int main() {
6| 27| rd rd;
7| 27| wt wt;
8| 27| int n = rd.uh();
9| 27| int q = rd.uh();
10| 27| int m = n / 16 + 1;
11| 27| int len = log(m) + 1;
12| 27| int table[len][m];
13| 27| int val[n];
14| 27| int suf[n];
15| 27| int pre[n];
16| 7.11M| for (int min, i = 0; i < n; ++i) {
^7.11M
------------------
| Branch (16:24): [True: 100.00%, False: 0.00%]
------------------
17| 7.11M| int id = i & 15;
18| 7.11M| int value = pre[i] = val[i] = rd.uw();
19| 7.11M| suf[i] = min = id ? std::min(min, value) : value;
^6.66M ^444k
------------------
| Branch (19:20): [True: 93.75%, False: 6.25%]
------------------
20| 7.11M| if (id == 15) table[0][i / 16] = suf[i];
^444k
------------------
| Branch (20:9): [True: 6.25%, False: 93.75%]
------------------
21| 7.11M| }
22| 7.11M| for (int min, i = n - 2; i >= 0; --i) {
^7.11M
------------------
| Branch (22:28): [True: 100.00%, False: 0.00%]
------------------
23| 7.11M| int id = ~i & 15;
24| 7.11M| int value = pre[i];
25| 7.11M| pre[i] = min = id ? std::min(min, value) : value;
^6.66M ^444k
------------------
| Branch (25:20): [True: 93.75%, False: 6.25%]
------------------
26| 7.11M| }
27| 248| for (int i = 1; i < len; ++i) {
^221
------------------
| Branch (27:19): [True: 89.11%, False: 10.89%]
------------------
28| 5.96M| for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
^5.96M
------------------
| Branch (28:39): [True: 100.00%, False: 0.00%]
------------------
29| 5.96M| table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
30| 5.96M| }
31| 221| }
32| 6.84M| while (q--) {
------------------
| Branch (32:10): [True: 100.00%, False: 0.00%]
------------------
33| 6.84M| int l = rd.uh();
34| 6.84M| int r = rd.uh() - 1;
35| 6.84M| int L = l / 16;
36| 6.84M| int R = r / 16;
37| 6.84M| int ans;
38| 6.84M| if (L == R) {
------------------
| Branch (38:9): [True: 2.98%, False: 97.02%]
------------------
39| 203k| ans = val[l];
40| 1.18M| for (int i = l + 1; i <= r; ++i) ans = std::min(ans, val[i]);
^983k^983k
------------------
| Branch (40:27): [True: 82.83%, False: 17.17%]
------------------
41| 6.63M| } else if (L == R - 1) {
------------------
| Branch (41:16): [True: 5.48%, False: 94.52%]
------------------
42| 363k| int p = pre[l];
43| 363k| int s = suf[r];
44| 363k| ans = std::min(p, s);
45| 6.27M| } else {
46| 6.27M| int p = pre[l];
47| 6.27M| int s = suf[r];
48| 6.27M| int k = log(R - L - 1);
49| 6.27M| int a = table[k][L + 1];
50| 6.27M| int b = table[k][R - (1 << k)];
51| 6.27M| ans = std::min({p, s, a, b});
52| 6.27M| }
53| 6.84M| wt.ud(ans);
54| 6.84M| }
55| 27| return 0;
56| 27|}