Submission #243481

#	Time	Username	Problem	Language	Result	Execution time	Memory
243481		AlexPop28	Secret (JOI14_secret)	C++11	100 / 100	515 ms	4600 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

int logn, size;
vector<vector<int>> st;

void Init(int n, int a[]) {
  logn = 32 - __builtin_clz(n);
  size = 1 << logn;
  st.resize(logn, vector<int>(size));
  
  for (int i = 0; i < n; ++i) {
    st[0][i] = a[i];
  }
    
  for (int h = 1; h < logn; ++h) {
    int half = 1 << h, full = 1 << (h + 1);
    for (int i = half; i < n; i += full) {
      st[h][i - 1] = a[i - 1];
      for (int j = i - 2; j >= i - half; --j) {
        st[h][j] = Secret(a[j], st[h][j + 1]);
      }
      st[h][i] = a[i];
      for (int j = i + 1; j < i + half; ++j) {
        if (j < n)
          st[h][j] = Secret(st[h][j - 1], a[j]);
        else
          st[h][j] = st[h][j - 1];
      }
    }
  }
}

int Query(int l, int r) {
  if (l == r)
    return st[0][l];
    
  int h = 31 - __builtin_clz(l ^ r);
  return Secret(st[h][l], st[h][r]);
}

• Subtask 1: 100 / 100