/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|   500k|  for (int min, i = 0; i < n; ++i) {
                                            ^500k
  ------------------
  |  Branch (16:24): [True: 100.00%, False: 0.00%]
  ------------------
   17|   500k|    int id = i & 15;
   18|   500k|    int value = pre[i] = val[i] = rd.uw();
   19|   500k|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^468k                  ^31.2k
  ------------------
  |  Branch (19:20): [True: 93.75%, False: 6.25%]
  ------------------
   20|   500k|    if (id == 15) table[0][i / 16] = suf[i];
                                ^31.2k
  ------------------
  |  Branch (20:9): [True: 6.25%, False: 93.75%]
  ------------------
   21|   500k|  }
   22|   500k|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^499k
  ------------------
  |  Branch (22:28): [True: 100.00%, False: 0.00%]
  ------------------
   23|   499k|    int id = ~i & 15;
   24|   499k|    int value = pre[i];
   25|   499k|    pre[i] = min = id ? std::min(min, value) : value;
                                      ^468k                  ^31.2k
  ------------------
  |  Branch (25:20): [True: 93.75%, False: 6.25%]
  ------------------
   26|   499k|  }
   27|     15|  for (int i = 1; i < len; ++i) {
                                         ^14
  ------------------
  |  Branch (27:19): [True: 93.33%, False: 6.67%]
  ------------------
   28|   421k|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
                                                           ^421k
  ------------------
  |  Branch (28:39): [True: 100.00%, False: 0.00%]
  ------------------
   29|   421k|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   30|   421k|    }
   31|     14|  }
   32|   500k|  while (q--) {
  ------------------
  |  Branch (32:10): [True: 100.00%, False: 0.00%]
  ------------------
   33|   500k|    int l = rd.uh();
   34|   500k|    int r = rd.uh() - 1;
   35|   500k|    int L = l / 16;
   36|   500k|    int R = r / 16;
   37|   500k|    int ans;
   38|   500k|    if (L == R) {
  ------------------
  |  Branch (38:9): [True: 7.73%, False: 92.27%]
  ------------------
   39|  38.6k|      ans = val[l];
   40|   231k|      for (int i = l + 1; i <= r; ++i) ans = std::min(ans, val[i]);
                                                ^193k^193k
  ------------------
  |  Branch (40:27): [True: 83.33%, False: 16.67%]
  ------------------
   41|   461k|    } else if (L == R - 1) {
  ------------------
  |  Branch (41:16): [True: 15.75%, False: 84.25%]
  ------------------
   42|  72.6k|      int p = pre[l];
   43|  72.6k|      int s = suf[r];
   44|  72.6k|      ans = std::min(p, s);
   45|   388k|    } else {
   46|   388k|      int p = pre[l];
   47|   388k|      int s = suf[r];
   48|   388k|      int k = log(R - L - 1);
   49|   388k|      int a = table[k][L + 1];
   50|   388k|      int b = table[k][R - (1 << k)];
   51|   388k|      ans = std::min({p, s, a, b});
   52|   388k|    }
   53|   500k|    wt.ud(ans);
   54|   500k|  }
   55|      1|  return 0;
   56|      1|}