/tmp/solutions/build/staticrmq-main.cpp:
    1|       |#include <common.h>
    2|       |#include <toy/bit.h>
    3|       |prelude;
    4|       |
    5|      1|int main() {
    6|      1|  rd rd;
    7|      1|  wt wt;
    8|      1|  int n = rd.uh();
    9|      1|  int q = rd.uh();
   10|      1|  int m = n / 16 + 1;
   11|      1|  int len = log(m) + 1;
   12|      1|  int table[len][m];
   13|      1|  int val[n];
   14|      1|  int suf[n];
   15|      1|  int pre[n];
   16|  53.3k|  for (int min, i = 0; i < n; ++i) {
                                            ^53.3k
  ------------------
  |  Branch (16:24): [True: 100.00%, False: 0.00%]
  ------------------
   17|  53.3k|    int id = i & 15;
   18|  53.3k|    int value = pre[i] = val[i] = rd.uw();
   19|  53.3k|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^50.0k                 ^3.33k
  ------------------
  |  Branch (19:20): [True: 93.75%, False: 6.25%]
  ------------------
   20|  53.3k|    if (id == 15) table[0][i / 16] = suf[i];
                                ^3.33k
  ------------------
  |  Branch (20:9): [True: 6.25%, False: 93.75%]
  ------------------
   21|  53.3k|  }
   22|  53.3k|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^53.3k
  ------------------
  |  Branch (22:28): [True: 100.00%, False: 0.00%]
  ------------------
   23|  53.3k|    int id = ~i & 15;
   24|  53.3k|    int value = pre[i];
   25|  53.3k|    pre[i] = min = id ? std::min(min, value) : value;
                                      ^50.0k                 ^3.33k
  ------------------
  |  Branch (25:20): [True: 93.75%, False: 6.25%]
  ------------------
   26|  53.3k|  }
   27|     12|  for (int i = 1; i < len; ++i) {
                                         ^11
  ------------------
  |  Branch (27:19): [True: 91.67%, False: 8.33%]
  ------------------
   28|  34.6k|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
                                                           ^34.6k
  ------------------
  |  Branch (28:39): [True: 99.97%, False: 0.03%]
  ------------------
   29|  34.6k|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   30|  34.6k|    }
   31|     11|  }
   32|   382k|  while (q--) {
  ------------------
  |  Branch (32:10): [True: 100.00%, False: 0.00%]
  ------------------
   33|   382k|    int l = rd.uh();
   34|   382k|    int r = rd.uh() - 1;
   35|   382k|    int L = l / 16;
   36|   382k|    int R = r / 16;
   37|   382k|    int ans;
   38|   382k|    if (L == R) {
  ------------------
  |  Branch (38:9): [True: 0.04%, False: 99.96%]
  ------------------
   39|    142|      ans = val[l];
   40|    871|      for (int i = l + 1; i <= r; ++i) ans = std::min(ans, val[i]);
                                                ^729 ^729
  ------------------
  |  Branch (40:27): [True: 83.70%, False: 16.30%]
  ------------------
   41|   382k|    } else if (L == R - 1) {
  ------------------
  |  Branch (41:16): [True: 0.06%, False: 99.94%]
  ------------------
   42|    243|      int p = pre[l];
   43|    243|      int s = suf[r];
   44|    243|      ans = std::min(p, s);
   45|   381k|    } else {
   46|   381k|      int p = pre[l];
   47|   381k|      int s = suf[r];
   48|   381k|      int k = log(R - L - 1);
   49|   381k|      int a = table[k][L + 1];
   50|   381k|      int b = table[k][R - (1 << k)];
   51|   381k|      ans = std::min({p, s, a, b});
   52|   381k|    }
   53|   382k|    wt.ud(ans);
   54|   382k|  }
   55|      1|  return 0;
   56|      1|}