Submission #1248924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248924		julia_08	Secret (JOI14_secret)	C++20	100 / 100	340 ms	4464 KiB

secret

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

using namespace std;

const int MAXN = 1e3 + 10;

int a[MAXN], mask[MAXN];

int val[10][MAXN];

void compute(int l, int r, int d, int cur_mask){

  if(l == r){
    mask[l] = cur_mask;
    return;
  }

  int m = (l + r) / 2;

  val[d][m] = a[m];
  if(m + 1 <= r) val[d][m + 1] = a[m + 1];

  for(int i=(m + 2); i<=r; i++) val[d][i] = Secret(val[d][i - 1], a[i]);
  for(int i=(m - 1); i>=l; i--) val[d][i] = Secret(a[i], val[d][i + 1]);

  compute(l, m, d + 1, cur_mask);
  compute(m + 1, r, d + 1, cur_mask + (1 << d));

}

void Init(int n, int a_[]){

  for(int i=0; i<n; i++) a[i] = a_[i];

  compute(0, n - 1, 0, 0);

}

int Query(int l, int r){

  if(l == r) return a[l];

  int d = __builtin_ctz(mask[l] ^ mask[r]);
  return Secret(val[d][l], val[d][r]);

}

• Subtask 1: 100 / 100