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