/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|}