제출 #703004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703004		BERNARB01	Secret (JOI14_secret)	C++17	100 / 100	468 ms	8404 KiB

secret

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

using namespace std;

const int N = 1003;

int n;
int a[N];
int precalc[N][N];

void PreCalc(int l, int r) {
  int y = (l + r) >> 1;
  precalc[y][y] = a[y];
  for (int i = y - 1; i >= l; i--) {
    precalc[i][y] = Secret(a[i], precalc[i + 1][y]);
  }
  precalc[y + 1][y + 1] = a[y + 1];
  for (int i = y + 2; i <= r; i++) {
    precalc[y + 1][i] = Secret(precalc[y + 1][i - 1], a[i]);
  }
  if (l < y) {
    PreCalc(l, y);
  }
  if (y + 1 < r) {
    PreCalc(y + 1, r);
  }
}

void Init(int N_, int A[]) {
  n = N_;
  for (int i = 0; i < n; i++) a[i] = A[i];
  PreCalc(0, n - 1);
}

int get(int l, int r, int ll, int rr) {
  if (ll == rr) {
    return a[ll];
  }
  int y = (l + r) >> 1;
  if (rr <= y) {
    return get(l, y, ll, rr);
  }
  if (ll > y) {
    return get(y + 1, r, ll, rr);
  }
  return Secret(precalc[ll][y], precalc[y + 1][rr]);
}

int Query(int ll, int rr) {
  return get(0, n - 1, ll, rr);
}

• Subtask 1: 100 / 100