Submission #1257072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257072		czauderna	Secret (JOI14_secret)	C++20	100 / 100	342 ms	4392 KiB

secret

#include "secret.h"

const int N = 1e3+3;
int opr[N][10], msk[N], Ar[N];

void pre(int l, int r, int lvl){
  if(l==r) return;
  int m = (l+r)/2;
  for(int i=l; i<=m; i++) msk[i] ^= 1<<lvl;
  opr[m][lvl] = Ar[m];
  for(int i=m-1; i>=l; i--) opr[i][lvl] = Secret(Ar[i], opr[i+1][lvl]);
  opr[m+1][lvl] = Ar[m+1];
  for(int i=m+2; i<=r; i++) opr[i][lvl] = Secret(opr[i-1][lvl], Ar[i]);
  pre(l, m, lvl+1);
  pre(m+1, r, lvl+1);
}

void Init(int N, int A[]) {
  for(int i=0; i<N; i++) Ar[i] = A[i];
  pre(0, N-1, 0);
}

int Query(int L, int R) {
  if(L == R) return Ar[L];
  int ms = msk[L]^msk[R];
  int lvl=__builtin_ctz(ms);
  return Secret(opr[L][lvl], opr[R][lvl]);
}

• Subtask 1: 100 / 100